0
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joffan
    Feb 11, 2021 at 21:55
  • $\begingroup$ @Joffan yes yes, I have remarked that on the body of the question. $\endgroup$
    – Anon142
    Feb 11, 2021 at 21:58

1 Answer 1

1
$\begingroup$

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)\equiv$$0\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}\ $?

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Anon142
    Feb 11, 2021 at 22:00
  • $\begingroup$ Do I need to divide it into cases of $s$? when $s=1$ and $s\neq 1$? I cannot see. $\endgroup$
    – Anon142
    Feb 11, 2021 at 22:15
  • $\begingroup$ 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? $\endgroup$ Feb 11, 2021 at 22:39
  • $\begingroup$ But $a^{t}$ can be -1 or 1. How do we know that he is always 1? $\endgroup$
    – Anon142
    Feb 11, 2021 at 22:53
  • $\begingroup$ 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}\ $. $\endgroup$ Feb 12, 2021 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.