Answer to Question #350948 in Combinatorics | Number Theory for WSN

Question #350948

5. Prove that "19|2^{2^{6k+2}}+3" for k = 0, 1, 2, .... 


1
Expert's answer
2022-06-27T05:08:35-0400

Since "gcd(4,19)=gcd(16,19)", then by Fermat's Little Theorem, "4^{19-1}\\equiv4^{18}\\equiv16^{18}\\equiv1(mod\\ 19)".

Let "P(k)" be the statement "2^{2^{6k+2}}\\equiv16(mod\\ 19)"

Proof by induction on "k" that "P(k)" is true for all "k\\geq0":

Base case: Let "k=0", then "2^{2^{6k+2}}\\equiv2^{2^{6\\cdot0+2}}\\equiv2^{2^2}\\equiv16(mod\\ 19)", hence "P(0)" is true.

Inductive step: Suppose "P(k)" is true, then "2^{2^{6k+2}}\\equiv16(mod\\ 19)", hence

"2^{2^{6(k+1)+2}}\\equiv2^{2^{6k+6+2}}\\equiv2^{2^{6k+2}\\cdot 2^6}\\equiv(2^{2^{6k+2}})^{2^6}\\equiv\\\\16^{2^6}\n\\equiv16^{64}\\equiv16^{3\\cdot18+10}\\equiv16^{10}\\equiv4^{20}\\equiv4^{18+2}\\equiv\\\\\n4^2\\equiv16(mod \\ 19)"

so "P(k)\\implies P(k+1)".

Thus, by induction, "P(k)" is true for all "k\\geq0."

Since "2^{2^{6k+2}}\\equiv16(mod\\ 19)", then

"2^{2^{6k+2}}+3\\equiv16+3(mod\\ 19)\\equiv19(mod\\ 19)\\equiv 0(mod\\ 19)", so "19|2^{2^{6k+2}}+3."


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS