What n satisfy 2^n == 3n+2 (mod n^2 - 2n)
The clue is to observe that n^2 - 2n = n(n-2). First note that n is necessarily odd, which means that n and n-2 are relatively prime. By the Chinese Remainder Theorem, the equation is equivalent to the following system of equations:
2^n == 2 (mod n) 2^n == 8 (mod n-2)
Since n-2 is odd, the second equation is equivalent to
2^{n-2} == 2 (mod n-2).
Thus n is a solution if and only if each of n and n-2 is a prime or a Sarrus/Poulet pseudoprime.
I hope someone will submit this to the OEIS! Neil
My puzzle, I'll do it. On 2/2/2012 12:26 PM, N. J. A. Sloane wrote:
What n satisfy 2^n == 3n+2 (mod n^2 - 2n) The clue is to observe that n^2 - 2n = n(n-2). First note that n is necessarily odd, which means that n and n-2 are relatively prime. By the Chinese Remainder Theorem, the equation is equivalent to the following system of equations: 2^n == 2 (mod n) 2^n == 8 (mod n-2) Since n-2 is odd, the second equation is equivalent to
2^{n-2} == 2 (mod n-2). Thus n is a solution if and only if each of n and n-2 is a prime or a Sarrus/Poulet pseudoprime. I hope someone will submit this to the OEIS!
Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
David Wilson -
N. J. A. Sloane