Question

Prove that \(2^{2^{n+1}} \equiv 1(mod~2^{2^n}} + 1\)
Please, help

Answer 1

\(2^{2^{n+1}} \equiv 1 (mod~2^{2^n} +1)\)

Answer 2

use the fact that a = b (mod m) ---> m*k = a-b to turn


2^(2^(n+1)) = 1 (mod 2^(2^n) + 1)

into

(2^(2^n) + 1)*k = 2^(2^(n+1)) - 1


if we can show k is an integer, then we've effectively proven the equation above is true


(2^(2^n) + 1)*k = 2^(2^(n+1)) - 1
(2^(2^n) + 1)*k = 2^(2^n*2^1)) - 1 ... note1
(2^(2^n) + 1)*k = 2^(2^n*2) - 1
(2^(2^n) + 1)*k = [2^(2^n)]^2 - 1 ... note2
(2^(2^n) + 1)*k = [2^(2^n) - 1][2^(2^n) + 1] ... note3
k = 2^(2^n) - 1 ... note4


so this proves k is indeed an integer since 2^(2^n) is an integer


note1: used the identity a^x*a^y = a^(x+y)
note2: used the identity (a^x)^y = a^(x*y)
note3: used the difference of squares factoring rule
note4: divided both sides by 2^(2^n) + 1

Answer 3

n is an integer
2^n is an integer (integer to any integer power = integer)
2^(2^n) is an integer
2^(2^n) - 1 is an integer (integer - integer = integer)

Answer 4

Got you. Thank you so much.

Answer 5

I need know the easiest way to solve \(3^{323} mod 17\). Please

Answer 6

hints
323 = 17*19
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Answer 7

and 19 = 17+2

so 3^19 = 3^(17+2) = 3^17*3^2

Answer 8

got it, too. :)