What are the possible remainders whenFn (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^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