Finding Natural Numbers n Satisfying a Congruence

[hadi amiri 4]

fin all natural numbers n that $$n\sigma (n) \equiv 2(mod\varphi(n))$$

 

[dodo]

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.

 

[hamster143]

4 and 6 do not comply:

4: n sigma(n) = 4*7 = 28, phi = 2
6: n sigma(n) = 6*12 = 72, phi = 2

 

[dodo]

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".

 

[hamster143]

Good point.

Either way, no other solutions for n up to 10^8.

 

[hamster143]

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.