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

Home > Numbers
Does it continue? 5: powers of 2 (Posted on 2017-09-24) Difficulty: 3 of 5
Before trying the problem "note your opinion as to whether the observed pattern is known to continue, known not to continue, or not known at all."

For integers greater than 1,
2n is never congruent to 1 (mod n)
2n is congruent to 2 (mod n) whenever n is prime, and sometimes when it isn't,
is 2n ever congruent to 3 (mod n)?

No Solution Yet Submitted by Jer    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution Showcasing Several Sequences | Comment 4 of 6 |
Noting my opinion: I already knew the answer to questions 2 and 3 and already conjectured question 1 to be true.

The values of 2^n mod n form a sequence, OEIS A015910. Casual inspection of the first two dozen terms would imply that all the values will be even, but at n=25 the value 2^25 mod 25 = 7.

So there are odd values, the first one occurs at n=25.  Are there others?  Yes, sequence OEIS A015911 lists values of n which make 2^n mod n equal an odd number.

Jer's third question asks is there is an n such that 2^n mod n = 3.  It takes a while to get to find a solution to 2^n mod n = 3, which occurs at n=4700063497.  This is quite a large number.  It turns out that there is significant interest in this specific equation that it has its own sequence OEIS A050259, for which we know only five nontrivial members.  We have also asked about it specifically on perplexus in the past in Power x mod x.

Since 2^n mod n can equal 3 is it the case that all integers can be the answer to the calculation?  This is conjectured to be true for all remainders greater than 1.  OEIS A036236 lists the smallest known n for each possible remainder.  The first comment addresses the possibility of the remainder 1, which is Jer's first question.  The statement proves there are no values by using some math above my level.

Jer's second question asks for numbers that make 2^n mod n equal to 2.  Anyone familiar with Fermat's Little Theorem will immediately know that any prime other than 2 will work.  The composite solutions are known as pseudoprimes to base 2, listed in OEIS A001567.

  Posted by Brian Smith on 2017-09-25 09:38:53
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 (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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