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)?
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.
Solution Showcasing Several Sequences
