Number Theory Help: Eulers phi function, LCM, and Modulos

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$.

Prove

$$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.

• Minor modification will be needed. If you want $k\ge 2$, then you have to specify that $b\gt 1$. – André Nicolas Nov 4 '13 at 19:14
• 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... – Cesar Nov 4 '13 at 19:20
• 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. – 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.