smallest prime divisor

[mahathir]

find the smallest prime divisor of \[12^{2^{15}}+1\]

[Masum]

That's a good application of order. Let $p$ be that prime. Then $12^{2^{15}}\equiv-1\pmod p$ or $12^{2^{16}}\equiv1\pmod p(\ast)$. Also by Fermat, $12^{p-1}\equiv1$. Let $d=ord_p(12)$. Then $d|p-1$. From $(\ast)$, $2^{16}$ is the smallest positive integer such that $(\ast)$ holds. By the definition of order, $d=2^{16}$. Then since $d|p-1,p\ge 2^{16}+1$. As $2^{2^4}+1=F_4$ is a known prime, $p=2^{16}+1$That's a good application of order. Let $p$ be that prime. Then $12^{2^{15}}\equiv-1\pmod p$ or $12^{2^{16}}\equiv1\pmod p(\ast)$. Also by Fermat, $12^{p-1}\equiv1$. Let $d=ord_p(12)$. Then $d|p-1$. From $(\ast)$, $2^{16}$ is the smallest positive integer such that $(\ast)$ holds. By the definition of order, $d=2^{16}$. Then since $d|p-1,p\ge 2^{16}+1$. As $2^{2^4}+1=F_4$ is a known prime, $p=2^{16}+1$