(In reply to
odd singledigit values for n under a billion by Charlie)
It has been conjectured that every nonnegative integer k is included in the set {2^n == k (mod n)} except k = 1.
The smallest nonnegative integer k such that 2^k mod k = 3 is 4700063497 (nearly five times larger than checked by Charlie's program).
The first several smallest nonnegative integers for n are given in OEIS A036236, and also provides the follwing proof by Max Alekseyev demonstrating that k = 1 does not exist in the set:
"Assume that there exists such n > 1. Consider its smallest prime divisor p. Then 2^n == 1 (mod p) implying that the multiplicative order ord_p(2) divides n. However, since ord_p(2) < p and p is the smallest divisor of n, we have ord_p(2) = 1, that is, p divides 2^1  1 = 1 which is impossible."
Edited on March 14, 2013, 2:05 am

Posted by Dej Mar
on 20130314 02:04:43 