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