This is mainly a correction, pointing out a lucuna. In the problem discussed below, a couple of us wondered (privately)
Why must N be odd?
After a bit of back & forth, it appears that N cannot be a multiple of 4, but the N = 4K+2 case is open. Note that even solutions of 2^N = 2 (mod N) exist, but are rare. Pinch's list of base 2 pseudoprimes < 10^13[?] included a small side list of even psps. Rich ------ Quoting Jakob Jonsson <jakobj@kth.se>:
On 23 Jan 2012, David Wilson asked:
What n satisfy 2^n == 3n+2 (mod n^2 - 2n)
On 30 Jan 2012, Hans Havermann wrote:
At first glance, except for n=5, these appear to be the greater of twin primes (A006512). However, on closer inspection, some n (563, 645, 647, 1105, 1907, 2467, 2701, 2821, 4371, 4373, 4681, 6601, ...) are clearly not.
(Spoilers ahead)
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.
Jakob
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
----- End forwarded message -----