All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 All but one (Posted on 2013-03-13)
Prove there is no positive integer n such that 2n divided by n gives a remainder of 1.

 See The Solution Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: odd single-digit values for n under a billion Comment 2 of 2 |
(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

 Search: Search body:
Forums (0)