Euler and Fermat

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\celsius }[0]{} \newcommand {\degree }[0]{} \newcommand {\ohm }[0]{} \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\tri }[0]{\triangle } \newcommand {\l }[0]{\ell } \newcommand {\P }[0]{\mathcal {P}} \newcommand {\R }[0]{\mathbb {R}} \newcommand {\Q }[0]{\mathbb {Q}} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\N }[0]{\mathbb N} \newcommand {\ph }[0]{\varphi } \newcommand {\vec }[0]{\mathbf } \newcommand {\d }[0]{\,d} \newcommand {\egmil }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_person.pdf}\hspace {0.5mm}}} \newcommand {\eghuntho }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_fish.pdf}\hspace {0.5mm}}} \newcommand {\egtentho }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_finger.pdf}\hspace {0.5mm}}} \newcommand {\egtho }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_lotus.pdf}\hspace {0.5mm}}} \newcommand {\eghun }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_scroll.pdf}\hspace {0.5mm}}} \newcommand {\egten }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_heel.pdf}\hspace {0.5mm}}} \newcommand {\egone }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_stroke.pdf}\hspace {0.5mm}}} \newcommand {\egyptify }[7]{ \multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_person.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#2}{\includegraphics [scale=.1]{egyptian/egypt_fish.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#3}{\includegraphics [scale=.1]{egyptian/egypt_finger.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#4}{\includegraphics [scale=.1]{egyptian/egypt_lotus.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#5}{\includegraphics [scale=.1]{egyptian/egypt_scroll.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#6}{\includegraphics [scale=.1]{egyptian/egypt_heel.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#7}{\includegraphics [scale=.1]{egyptian/egypt_stroke.pdf}\hspace {0.5mm}} \hspace {.5mm} } \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\degree }[0]{\ensuremath {^\circ }} \newcommand {\celsius }[0]{\ifmmode ^\circ \mathrm {C}\else $^\circ $C\fi } \newcommand {\ohm }[0]{\ifmmode \Omega \else $\Omega $\fi }$

Remind me: what are the necessary ingredients for a proof by induction?

Our goal is to prove the following theorem:

Suppose that $a$ is an even number and $p$ a prime which does not divide $a$ . Suppose that $p$ does divide $a^{2^n} + 1$ . Then $p$ is of the form $p = 2^{n+1}k + 1$ for some positive integer $k$ .

In order to prove this theorem, we’ll need the so-called “Little Fermat Theorem”. You can find Euler’s proof of this theorem in your text.

Little Fermat Theorem Let $a$ be a whole number and $p$ a prime which does not divide $a$ . Then $p$ divides $a^{p-1} - 1$ .

Remind me: what is the definition of “divides”?

Prove that Theorem EFT is true in the case that $n=0$ .

(Divisor Question) Suppose that $A$ is any whole number, and that you divide $A$ by some number $C$ . What are the possible remainders? What are the possibilities for how you could write $A$ as related to a multiple of $C$ ?

(Cases Question) Repeat the divisor question, but related to Theorem EFT and the case $n=1$ . In other words, what are the possibilities for the prime $p$ when you divide by $2^2 = 4$ ? Then, eliminate all but two of these cases.

(Contradiction Question) Use proof by contradiction to eliminate the case you don’t want.

Repeat the cases question and the divisor question, but for the case $n=2$ . If you’re confident you understand what’s going on, move to the next question!

Prove Theorem EFT.

Euler used Theorem EFT to prove that $2^{2^5}+1$ is not prime. How did he do this? Check his work. Could you use his method to prove that $2^{2^6} +1$ is not prime?