fin all natural numbers n that [tex]n\sigma (n) \equiv 2(mod\varphi(n)) [/tex]
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.
4 and 6 do not comply:
4: n sigma(n) = 4*7 = 28, phi = 2
6: n sigma(n) = 6*12 = 72, phi = 2
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".
Either way, no other solutions for n up to 10^8.
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.
Separate names with a comma.