Question

Find highest n that returns a remainder of zero:
((7^n)+1)/2^n

Answer 1

It works for n=0,1,3
I calculated up to n=7

Answer 2

Python says 3 is the highest n under 1000.

Answer 3

what is Python?

Answer 4

A programming language.

Answer 5

Thanks for the info. I guess it much more productive to run a little program instead of doing it manually :-)

Answer 6

That's what computers are for! ;)

Here's the code, if you're curious:
for n in range(0, 1000):
if (7**n+1) % (2**n) == 0:
print n
(The ** operator means exponentiation, and % means mod.)

But I guess the real question is why n=3 the highest? That one's a bit of a thinker.

Answer 7

OK, thanks for the code, but can I run that code on my computer?

Answer 8

If you download and install python you can. Otherwise, try this: http://codepad.org/yq5LuMze
You can edit the code and resubmit it (make sure Run Code is checked) and it will run the code and show you the output. But I just tried modifying the limit to be 10k and it timed out. But you can play around with it a little.

Answer 9

Thank you so much, dmancine. I will try to explore it in a while and will let you know about my experience with Python. Now I need to go. Have a good time and thanks again for so much good and detailed info. I saved it in a file.

Answer 10

Through experimentation we found n=3 was the max. That meant that for any n>=4 that 7^n + 1 would not have n 2's in its prime factorization. So, I decided to look at the prime factorizations of 7^n + 1. They followed this pattern:
n=0: 2*odd
n=1: 8*odd
n=2: 2*odd
n=3: 8*odd
n=4: 2*odd
n=5: 8*odd
For even n's it was divisible by 2, and for odd n's it was divisible by 8. No higher powers of 2 appeared (for n < 20). So, I decided to look at 7^n + 1 mod 16 (since it never appeared to be divisible by 16).
n=0: 2
n=1: 8
n=2: 2
n=3: 8
n=4: 2
n=5: 8

That led me to hypothesize:
If 7^n+1mod16=2, then 7^(n+1)+1mod16=8, and
if 7^n+1mod16=8, then 7^(n+1)+1mod16=2.
Showing that these hold, along with the fact that 7^0 + 1 mod 16 = 2, will start the cycle going, and show that for n>3 there is no hope of 7^n + 1 being divisible by 2^n.

Answer 11

Given: 7^n + 1 mod 16 = 2.
Prove: 7^(n+1) + 1 mod 16 = 8.
7^n + 1 mod 16 = 2
7^n + 1 = 16x + 2
7^n = 16x + 1
7^(n+1) + 1 = 7(7^n) + 1 = 7(16x+1)+1 = 112x + 8 = 16(7x) + 8
So 7^(n+1)+1mod16=8

Given: 7^n + 1 mod 16 = 8.
Prove: 7^(n+1) + 1 mod 16 = 2.
7^n + 1 mod 16 = 8
7^n + 1 = 16x + 8
7^n = 16x + 7
7^(n+1) + 1 = 7(7^n) + 1 = 7(16x+7)+1 = 112x + 50
= 112x+48+2 = 16(7x+3) + 2
So 7^(n+1)+1mod16=2

Thus, 7^n + 1 for n>3 is never divisible by 16, much less by any higher power of 2. Therefore n=3 is the maximum value of n which satisfies the original condition.

Answer 12

And, just to be explicit, in the above proof,
\[x \in \mathbb{Z}\]And, since the integers are closed under multiplication and addition,\[7x \in \mathbb{Z}\]and\[7x+3 \in \mathbb{Z}\]so the mod assertions hold.

Answer 13

I came up with a longer and less efficient solution, I attached the pdf. The answer is 3. Thanks everyone!