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

Home > Numbers
All but one (Posted on 2013-03-13) Difficulty: 2 of 5
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.)
Some Thoughts 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

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information