Assume that $r$ and $s$ are relatively prime positive integers and that $n =rs$. Let $m = \mbox{lcm}(\phi(s), \phi(r))$ and assume that $\mbox{gcd}(a,n)=1$.


$$a^m \equiv 1 \bmod{r} \mbox{ and } a^m \equiv 1 \bmod{s}.$$

Now suppose that = $2^kb$ where $k\ge 2$ and $b$ is odd. Use the fact that $a^m \equiv 1 \bmod n$ - similar to before - to show that $\mbox{ord}_n(a) < \phi(n)$.

Sorry for bad form, this is my first time using this website.

  • $\begingroup$ Minor modification will be needed. If you want $k\ge 2$, then you have to specify that $b\gt 1$. $\endgroup$ – André Nicolas Nov 4 '13 at 19:14
  • $\begingroup$ yeah i have that in mind. I also just figured out how to prove the first part. It came to be not too long after posting this... $\endgroup$ – Cesar Nov 4 '13 at 19:20
  • $\begingroup$ but as to the second part. I really have no idea how to start it, i dont know how using the fact they gave me applies to the proof of it on its own. $\endgroup$ – Cesar Nov 4 '13 at 19:21

Because $m$ is a common multiple of $\varphi(r)$ and $\varphi(s)$, we have in particular that $m=q\varphi(r)$ for some $q$.

Since $\gcd(a,n)=1$, we have $\gcd(a,r)=1$. By Euler's Theorem, we have $$a^{\varphi(r)}\equiv 1\pmod{r}.$$ Thus $$a^m=(a^{\varphi(r)})^q\equiv 1\pmod{r}.$$ Similarly, we have $a^m\equiv 1\pmod{s}$. It follows that $a^m\equiv 1\pmod{rs}$.

Now we deal with the question about $n=2^k b$. We will need to assume that $b\gt 1$. For note that $-1$ has order $2$, that is, $\varphi(4)$, modulo $4$.

Suppose that $b\gt 1$. Since $b\ge 3$, $\varphi(b)$ is even. Also, $\varphi(2^k)=2^{k-1}$. Thus $\varphi(b)$ and $\varphi(2^k)$ are not relatively prime. So their lcm $m$ is less than $\varphi(2^k)\varphi(b)$, that is $m\lt\varphi(n)$. By the first part of the problem, $a$ has order $\le m$ modulo $n$, so the order of $a$ is indeed less than $\varphi(n)$.

Remark: If $b=1$ and $k\ge 3$, then $a$ has order $\lt \varphi(2^k)$ modulo $2^k$. The proof is not hard, but you probably are expected to take $b\gt 1$, so we omit the proof.


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.