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.

  Submitted by Jer    
No Rating
Solution: (Hide)

a(1) = 0, that is, no n exists with 2^n mod n = 1. Proof. 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. [From Max Alekseyev]

Comments: ( You must be logged in to post comments.)
  Subject Author Date
Some Thoughtsre: odd single-digit values for n under a billionDej Mar2013-03-14 02:04:43
Some Thoughtsodd single-digit values for n under a billionCharlie2013-03-14 00:10:02
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 (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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