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. 
 A: 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. 
