chaotic_iak wrote: Suppose that $m$ and $k$ are non-negative integers, and $p = 2^{2^m}+1$ is a prime number. Prove that (a) $2^{2^{m+1}p^k} \equiv 1$ $(\text{mod } p^{k+1})$; (b) $2^{m+1}p^k$ is the smallest positive integer $n$ satisfying the congruence equation $2^n \equiv 1$ $(\text{mod } p^{k+1})$. It follows directly from the lifting exponent Lemma , and it says that if $a\equiv b \pmod p$ Then $v_p(a^n-b^n)=v_p(a-b)+v_p(n)$ where $v_p(n)$ is the highest power such that $p^{v_p(n)} \mid n$ in other words $v_p(n)=a$ iff $ p^a \mid n$ and $p^{a+1}\not | n$

Abdek wrote: chaotic_iak wrote: Suppose that $m$ and $k$ are non-negative integers, and $p = 2^{2^m}+1$ is a prime number. Prove that (a) $2^{2^{m+1}p^k} \equiv 1$ $(\text{mod } p^{k+1})$; (b) $2^{m+1}p^k$ is the smallest positive integer $n$ satisfying the congruence equation $2^n \equiv 1$ $(\text{mod } p^{k+1})$. It follows directly from the lifting exponent Lemma , and it says that if $a\equiv b \pmod p$ Then $v_p(a^n-b^n)=v_p(a-b)+v_p(n)$ where $v_p(n)$ is the highest power such that $p^{v_p(n)} \mid n$ in other words $v_p(n)=a$ iff $ p^a \mid n$ and $p^{a+1}\not | n$ Uh... I don't understand. Can you explain it more clearly?

For lifting the exponent lemma,see this; and the conclusion will follow after you let the $ord_{p^{k+1}}(2)=n,$then $n=2^{m+1}p^k$

Lemma: $ord_{p^{k+1}}(c)=ord_{p}(c).p^k$ where $Gcd(c,p)=1$ Proof:From lifting the exponent lemma,we can easily note that this follows directly. Now $p$ is obviously odd,so $Gcd(p,2)=1$.so setting $c=2,$we find the result since here,$ord_p(2)=2^{m+1}$

For LTE, see this as well.

Would it be possible to use basic binomial theorem for this? (For those who don't know the lemma)

Solution: 1st part is trivial:$2^{2^m} \equiv -1\pmod{p} \implies 2^{2^{m+1}} \equiv 1\pmod{p} \implies 2^{2^{m+1}p^k} \equiv 1\pmod{p^{k+1}}$.\ 2nd part:Let $l$ be the oder of $2$ modulo $p^{k+1}$.From first part it follows that $l \mid 2^{m+1}p^k$.Next note that $2^{m+1}$ is the order of $2$ modulo $p$.For if $2^s$ with $0<s<k+1$ is the order then follows that $2^m \equiv 1\pmod{p}$,a contradiction.Thus it follows that $2^{m+1} \mid l$.Combining these details it follows that $l=2^{m+1}p^{j}$ for some $0 \le j \le k$.Now applying LTE we get: ${v_p(2^{2^{m+1}p^j}-1)=v_p(2^{2^{m+1}}-1)+v_p(p^j) =v_p((2^{2^m}-1)(2^{2^m}+1)}+j=1+j \ge k+1 \implies j \ge k$. From all these we conclude that the order of $2$ modulo $p^{k+1}$ is $2^{m+1}p^k$.

Part I: We will first prove a lemma. Lemma: $2^{2^{m+1}}-1\equiv 0\pmod p$. Proof: Consider the expression $(2^{2^m}+1)^2 \pmod p$. This satisfies $0 \equiv (2^{2^m}+1)^2\equiv 2^{2^{m+1}}+2\cdot 2^{2^m}+1\equiv 2^{2^{m+1}} 2^{2^{m+1}}-1$, so we are done. $\Box$ Now to prove that $2^{2^{m+1}p^k}\equiv 1 \pmod {p^{k+1}}$, we will use Lifting the Exponent Lemma. We must prove that $\nu_p(2^{2^{m+1}p^k}-1)\ge k+1$. By LTE, $\nu_p(2^{2^{m+1}p^k}-1)=\nu_p((2^{2^{m+1}})^{p^k}-(1)^{p^k})$, which is $\nu_p(2^{2^{m+1}}-1)+k$. But $p|2^{2^{m+1}}-1$, so we are done. $\blacksquare$ Part II: I will show that $\text{ord}_{p^{k+1}}(2)\not |2^{m}p^k$ and $\text{ord}_{p^{k+1}}(2)\not |2^{m+1}p^{k-1}$ using the Lifting the Exponent Lemma. Case I: $\text{ord}_{p^{k+1}}(2)\not |2^{m}p^k$. Proof: Assume that $2^{2^{m}p^k}-1\equiv 0\pmod {p^{k+1}}$. This implies that $\nu_p(2^{2^mp^k}-1)=\nu_p(2^{2^m}-1)+k\ge k+1$; that is, $p|2^{2^m}-1$. But this is a clear contradiction, as $p$ is odd. $\Box$ Case II: $\text{ord}_{p^{k+1}}(2)\not |2^{m+1}p^{k-1}$. Proof: Assume that $2^{2^{m+1}p^{k-1}}-1\equiv 0\pmod {p^{k+1}}$. This means that $\nu_p(2^{2^{m+1}p^{k-1}}-1)\ge k+1$. Since $\nu_p(2^{2^{m+1}p^{k-1}}-1)=\nu_p(2^{2^{m+1}}-1)+(k-1)$, it suffices to show that $p^2|2^{2^{m+1}}-1$. But this implies that $p^2|2^{2^m}+1$, contradiction. $\Box$ Since $\text{ord}_{p^{k+1}}(2)\not |2^{m}p^k$ and $\text{ord}_{p^{k+1}}(2)\not |2^{m+1}p^{k-1}$, and by Part I, $ 2^{2^{m+1}p^k}\equiv 1 (\text{mod }p^{k+1}) $, we are done. $\blacksquare$

Define $a=2^{2^m}$ and $b=-1.$ Then note that $a-b=2^{2^m}-(-1)=2^{2^m}+1=p$, so $p\mid a-b.$ Additionally, the Euclidean Algorithm gives \begin{align*} \gcd(p,ab)&=\gcd(2^{2^m}+1,-2^{2^m})\\ &=\gcd(1,-2^{2^m})\\ &=1. \end{align*}Thus $p\mid a-b$ and $\gcd(p,ab)=1$, so we can apply the LTE Lemma with the prime $p$ as the base, so that $$\nu_p(a^{p^k}-b^{p^k})=\nu_p(p^k)+\nu(a-b).$$Since $p$ is odd, so is $p^k$, so that $-b^{p^k}=-(-1)^{p^k}=-(-1)=1.$ Since $a-b=p$, the above equation simplifies to $$\nu_p((2^{2^m})^{p^k}-(-1)^{p^k})=\nu_p(p^k)+\nu_p(p),$$or $$\nu_p(2^{2^mp^k}+1)=k+1.$$ Taking modulo $p^{k+1}$, the above result implies that $2^{2^mp^k}+1\equiv0\pmod{p^{k+1}},$ so $$2^{2^mp^k}\equiv-1\pmod{p^{k+1}}.$$Squaring gives $2^{2(2^mp^k)}\equiv1\pmod{p^{k+1}},$ and equivalently $$2^{2^{m+1}p^k}\equiv1\pmod{p^{k+1}}.$$The above equation implies that $\text{ord}_{p^{k+1}}(2)\mid2^{m+1}p^k$; however, since we have shown previously that we have $2^{2^mp^k}\equiv-1\not\equiv1\pmod{p^{k+1}},$ it follows that the $\nu_2(\text{ord}_{p^{k+1}}(2))=m+1,$ so that the order of $2$ modulo $p^{k+1}$ must be of the form $2^{m+1}p^i$ for some $i\in\{0,1,\cdots,k\}.$ We apply the LTE Lemma one more time. This time, let $c=2^{2^{m+1}}$ and $d=1$, so that, due to difference of squares, \begin{align*} c-d&=2^{2^{m+1}}-1\\ &=(2^{2^m}+1)(2^{2^m}-1)\\ &=p(p-2), \end{align*}so that $c=p(p-2)+d=p(p-2)+1=p^2-2p+1=(p-1)^2.$ Also, \begin{align*} \gcd(p,cd)&=\gcd(p,(p-1)^2)\\ &=1, \end{align*}implying that $p\mid c-d$ and $\gcd(p,cd)=1.$ Hence, we can apply the LTE Lemma, giving $$\nu_p(c^{p^i}-d^{p^i})=\nu_p(p^i)+\nu_p(c-d).$$Substituting in $c-d=p(p-2),$ so that $\nu_p(c-d)=\nu_p(p(p-2))=1,$ gives $$\nu_p(2^{2^{m+1}p^i}-1)=i+1.$$ Because we have defined $\text{ord}_{p^{k+1}}(2)=2^{m+1}p^i$, it follows that $2^{2^{m+1}p^i}\equiv1\pmod{p^{k+1}},$ so that $$2^{2^{m+1}p^i}-1\equiv0\pmod{p^{k+1}},$$implying that $$\nu_p(2^{2^{m+1}p^i})\ge k+1.$$However, since we have previously found using the LTE Lemma that $\nu_p(2^{2^{m+1}p^i}-1)=i+1,$ it follows that $i+1\ge k+1$, or $i=k$ since $i\in\{0,1,\cdots,k\}.$ Hence, we conclude that $$\text{ord}_{p^{k+1}}(2)=2^{m+1}p^k,$$and we are done. $\blacksquare$

from the first one by mod p we have $2^{2^m} \equiv -1 \mod p$ thus $2^{2^{m+1}}\equiv 1 \mod p$ by lifting $v_p(2^{{2^{m+1}*p^k}}-1)=v_p(p^k)+v_p(2^{2^{m+1}}-1) = k+1$ since $v_p(ab) = v_p(a)+v_p(b) = v_p(2^{2^m}+1)+v_p(2^{2^m}-1)=v_p(2^{2^m}+1)=v_p(p)=1$ for second part $2^n \equiv 1 \mod p$ notice we already have $2^{2^m} \equiv -1 \mod p$ thus we know there order is $2^{m+1}$ $v_p(2^{2^{m+1}*n}-1) = v_p(n)+v_p(2^{2^{m}}+1)\geq k+1$ $v_p(n)+1 \geq k+1$ implies $n \geq p^k$