Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A good problem

  1. Nov 20, 2009 #1
    fin all natural numbers n that [tex]n\sigma (n) \equiv 2(mod\varphi(n)) [/tex]
  2. jcsd
  3. Nov 20, 2009 #2
    This is true for all primes, since n(n+1)-2 = (n+2)(n-1). The interesting part is, which non-primes are also in the list.

    Edit: under one million, only 1,4,6,22 comply. Hmmm.
    Last edited: Nov 20, 2009
  4. Nov 21, 2009 #3
    4 and 6 do not comply:

    4: n sigma(n) = 4*7 = 28, phi = 2
    6: n sigma(n) = 6*12 = 72, phi = 2
    Last edited: Nov 21, 2009
  5. Nov 21, 2009 #4
    I understood the condition as "both n . sigma(n) and 2 having the same residue modulo phi(n)", and not as "the residue of n . sigma(n) modulo phi(n) is 2".
  6. Nov 21, 2009 #5
    Good point.

    Either way, no other solutions for n up to 10^8.
  7. Nov 21, 2009 #6
    Okay, here's the condensed proof.

    First we need a lemma. If a == b (mod c) and b!=0, then |b| >= gcd(a,c). Specifically, if a == 2 (mod c), then a and c have no common factors greater than 2.

    Factorize n and plug in the expressions for phi and sigma in terms of prime factors into the equation.

    If any prime p>2 is present in the factorization more than once, LHS is a multiple of p and RHS is a multiple of p: no solution.

    If there's more than one prime p>2 in the factorization, or if n is a multiple of 8, LHS is a multiple of 4 and RHS is a multiple of 4: no solution.

    That leaves us with three sets of possibilities, n=p, n=2p, n=4p, where p is a prime >2, and a fourth possibility n=4.

    n=p always comply.

    n=4p don't comply because LHS and RHS are multiples of 4.

    n=2p comply iff n sigma(n) = 6p^2+6p == 2 (mod p-1)

    which is the same as 10 == 0 (mod p-1) which is true for p=2, p=3 and p=11, yielding solutions n=4, n=6, n=22.
    Last edited: Nov 21, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook