Prove there is no positive integer n such that 2ⁿ divided by n gives a remainder of 1.

(In reply to odd single-digit values for n under a billion by Charlie)

It has been conjectured that every non-negative integer k is included in the set {2^n == k (mod n)} except k = 1.

The smallest non-negative 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 non-negative 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 2013-03-14 02:04:43