1. ## Fermat"s Theorem

What are the possible remainders when
Fn (the nth Fermat number Fn := 2^2n + 1,

n
¸
1) is divided by (a). 3, (b). 7, (c). 9?

I know the Fermat number is defined as 2^(2n)+1, but have trouble in finding possible remainders.

Like I can find F_0=2^0+1=2, so remainder when dived by 3 is 1, 5 when divided by 7, 7 when divided by 9
I guess I could continue in this method, but might there be an easier way to do this?

2. Originally Posted by mathematic
What are the possible remainders when
Fn (the nth Fermat number Fn := 2^2n + 1,

n
¸
1) is divided by (a). 3, (b). 7, (c). 9?

I know the Fermat number is defined as 2^(2n)+1, but have trouble in finding possible remainders.

Like I can find F_0=2^0+1=2, so remainder when dived by 3 is 1, 5 when divided by 7, 7 when divided by 9
I guess I could continue in this method, but might there be an easier way to do this?

I can help with a) and b), but I'm not certain of my method for c) because 9 is not a prime. (I haven't actually tried it in mod 9.)

Since $2 \equiv -1 ~\text{(mod 3)}$

$\dsiplaystyle 2^{2n} + 1 \equiv (-1)^{2n} + 1 \equiv 1^{n} + 1 \equiv 1 + 1 \equiv 2 ~\text{(mod 3)}$

So 2 is the only remainder.

You can do this for part b) as well. I get possible remainders of 2, 3, and 5.

-Dan

3. 2=2 mod 7
so (2)^(2n)+1=2^2*2^n+1=4*2^n+1

4. Here's the corrected version.

$\displaystyle F_n = 2^{2^n}+1$

mod 3:

$2^n \equiv \{1,~2 \}~\text{(mod 3)}$

Thus
$2^{2^n} + 1 \equiv 2^{2^1} + 1 \equiv 2$

or
$2^{2^n} + 1 \equiv 2^{2^2} + 1 \equiv 2$

The process for mod 7 is similar. I get 3, 5 for answers now. Again I don't know how to approach mod 9.

-Dan

Of course this is all for n > 0...

5. 2^1=1 mod7
2^2=4 mod 7
2^3=8=1 mod 7
2^4=16=2 mod 7
2^5=32=4 mod 7
2^6=64=1 mod 7
2^7=128=2 mod 7
so 2^n={1,2,4} mod 7

2^(2^1)+1=2^2+1=4+1=5mod 7
2^(2^2)+1=2^4+1=16+1=17=3 mod 7
2^(2^4)+1=2^16+1=65,356+1=65,357=2 mod 7

For 9
2^1=2 mod 9
2^2=4 mod 9
2^3=8 mod 9
2^4=16=7mod9
2^5=32=5 mod 9
2^6=64=1 mod 9
2^7=2 mod 9
2^8=4 mod 9
2^9=8 mod 9
So 2^n={1,2,4,5,7,8}
2^(2^1)+1=4+1=5 mod 9
2^(2^2)+1=16+1=17=8 mod 9
2^(2^4)+1=8 mod 9
2^(2^5)+1=5 mod9
2^(2^7)+1=
so remainders are 5 and 8

6. Originally Posted by mathematic
2^(2^4)+1=2^16+1=65,356+1=65,357=2 mod 7
65537 = 3 (mod 7)

-Dan

7. i rechecked and now I'm getting 65,357=5 mod 7

8. oh, it should be 65,537
ok i get 3 now

9. Originally Posted by mathematic
For 9
2^1=2 mod 9
2^2=4 mod 9
2^3=8 mod 9
2^4=16=7mod9
2^5=32=5 mod 9
2^6=64=1 mod 9
2^7=2 mod 9
2^8=4 mod 9
2^9=8 mod 9
So 2^n={1,2,4,5,7,8}
2^(2^1)+1=4+1=5 mod 9
2^(2^2)+1=16+1=17=8 mod 9
2^(2^4)+1=8 mod 9
2^(2^5)+1=5 mod9
2^(2^7)+1=
so remainders are 5 and 8
It is, of course, possible to do it this way, but I was hoping to find something more efficient given that 9 = 3*3. But it does work.

-Dan