# Congruence question and prime numbers

Let $$p$$ be an odd prime number when $$p-1=2^{s}\cdot t$$, $$s\in \mathbb{N}, t\in \mathbb{Z}$$ and $$t$$ is odd. Need to prove that if $$(a,p)=1$$, then $$a^{t}\equiv 1 \pmod{p}$$ or $$a^{2^{i}\cdot t}\equiv -1 \pmod{p}$$, for $$0\le i\le s-1$$. In addition $$a\in \mathbb{Z^{+}}$$.

My attempt: suppose that $$(a,p)=1$$ and $$p-1=2^{s}\cdot t$$. Since $$0\le i\le s-1$$ then let $$s=i+x$$, for $$x\in \mathbb{N}$$. According to little's Fermat theorem, since $$(a,p)=1$$ we have that: $$a^{p-1}\equiv 1 \pmod{p}$$. Recall that $$p-1=2^{s}\cdot t$$ so by substitution - $$a^{p-1}\equiv a^{2^{s}\cdot t}\equiv 1 \pmod{p}$$. Now by substitution of $$s=i+x$$ we get: $$a^{2^{i}\cdot 2^{x}\cdot t}\equiv (a^{2^{i}\cdot 2^{x}})^{t}\equiv (a^{2^{i}\cdot t})^{2^{x}}\equiv 1 \pmod{p}$$. From here I don't know how to proceed, but I still didn't use the definition of t and p being odd prime numbers. Therefore I will be glad to get some help. Thanks!

• Note that $t$ is odd but not necessarily prime (to clarify your last remark there). And you did use the primality of $p$ once anyway, in invoking Fermat's little theorem. Feb 11, 2021 at 21:55
• @Joffan yes yes, I have remarked that on the body of the question. Feb 11, 2021 at 21:58

Hint

If $$\ a^{2^st}\equiv1\pmod{p}\$$, then $$\ \left(a^{2^{s-1}t}-1\right)\left(a^{2^{s-1}t}+1\right)\equiv0\pmod{p}\$$, so either $$\ a^{2^{s-1}t}\equiv1\pmod{p}\$$ or $$\ a^{2^{s-1}t}\equiv-1\pmod{p}\$$. If the second alternative holds, you're home. Otherwise, now play the same game with $$\ s-1\$$ in place of $$\ s\$$.

Hint for another approach

Here's another approach which you might find easier. The multiplicative order $$\ \sigma\$$ of $$\ a\$$ mod $$\ p\$$ must be a divisor of $$\ p-1=2^st\$$—that is $$\ \sigma=2^jv\$$, where $$\ 0\le j\le s\$$ and $$\ t=vw\$$ with $$\ v\$$ and $$\ w\$$ both odd. If $$\ j=0\$$, what is $$\ a^v\pmod{p}\$$? What then is $$\ a^{vw}=a^t\pmod{p}\$$? If $$\ j\ge1\$$ and $$\ i=j-1\$$, what is $$\ a^{2^iv}\pmod{p}\$$? What then is $$\ a^{2^ivw}=a^{2^it}\pmod{p}\$$?

• I thought exactly doing so, but I don't know why I have changed my mind. Thanks! I am gonna give the hint a try. Feb 11, 2021 at 22:00
• Do I need to divide it into cases of $s$? when $s=1$ and $s\neq 1$? I cannot see. Feb 11, 2021 at 22:15
• Define $\ u=\min\left\{j\in\{0,1,\dots,s\}\,|\,a^{2^jt}\equiv1 \pmod{p}\right\}\$. Since the set $\ \left\{j\in\{0,1,\dots,s\}\,|\,a^{2^jt}\equiv1 \pmod{p}\right\}\$ is finite and non-empty (since $\ s\$ is in it), its minimum is well defined, and belongs to the set. If $\ u=0\$, what is $\ a^t\$ congruent to? If $\ u>0\$, what is $\ a^{2^{u-1}t}\$ congruent to? Feb 11, 2021 at 22:39
• But $a^{t}$ can be -1 or 1. How do we know that he is always 1? Feb 11, 2021 at 22:53
• No, if $\ u>1\$ (where $\ u\$ is defined as in my previous comment) then $\ a^t\$ will be neither $\ 1\$ nor $\ -1\$ mod $\ p\$, but in that case $\ a^{2^it}\equiv-1\pmod{p}\$, where $\ 0\le i=u-1\le s-1\$, so it will be the other alternative of the given conditions which holds in this case. If $\ u=1\$, then it will be the case that $\ a^t\equiv-1\pmod{p}\$, but then you still have $\ a^{2^it}\equiv-1\pmod{p}\$ for some $\ i\in\{0,1,\dots,s-1\}\$—namely for $\ i=0\$. Only in the case when $\ u=0\$ will it be true that $\ a^t\equiv1\pmod{p}\$. Feb 12, 2021 at 0:43