Suppose n has an odd prime divisor $p$ and $n$ is not of the form $p^k$ or $2p^k$. Show that there is no primitive root mod n.
Stuck on how to show this. Tried utilizing hints as I was given but still not sure.
Letting $k$ be the exponent of $p$ in the prime factorization of $n$ ($p_1^{c_1},...,p_k^{c_k}$), write $n = p^{k}n^{'}$. Then $\phi(n) = \phi(p^k)\phi(n^{'})$ and both $\phi(p^k)$ and $\phi(n^{'})$ are even. Using the Chinese Remainder Theorem, can argue for any $a$ with $gcd(a,n) = 1$, the order of $a\ mod\ n$ is $\leq lcm(\phi(p^k), \phi(n^{'})$), which is strictly less than $\phi(n)$.
So firstly, I'm not sure why both $\phi(p^k)$ and $\phi(n^{'})$ are even. If I had to guess, it has something to do with n not being of the form $2p^k$ and $2$ being the only even prime.
Would appreciate someone to help me fill in the blanks as I'm pretty stuck.
If $a$ is a primitive root $\mod n$, then $n=p^k$ or $n=2p^k$ where $p$ is an odd prime. The easy way to show this is by Euler's Theorem and the Carmichael Function. Euler's theorem states that for any integer $n$, $a^{ϕn} = 1 \pmod n$. Assume $n=2p^k$ has at least one other odd prime factor $q$ (not nessesarily distinct). Then $n=2qp^k$. $ϕn=ϕp^kϕ2ϕq=ϕp^kϕq=(p-1)(q-1)p^{k-1}$. Since $p, q$ are odd, $p=s2^t$ and $q=r2^v$ with $s, r$ odd. Then simplifying $ϕn$ above, one gets $ϕn=sr2^t2^vp^k$. Clearly either $t > v$, $t = v$, or $v > t$. If $t = v$, then $sr2^tp^k | (p-1)(q-1)p^k$ and it is the smallest such integer $x$ such that $a^{x}=1\pmod n$, implying no primitive root $\pmod n$ exists. Otherwise when $t > v$ or $v > t$, then either $2^t | 2^v$, or vise versa, and again, either $x = sr2^tp^k$ or $x = sr2^vp^k$. There are no primitive roots $\pmod 8$ as $1^2=3^2=5^2=7^2=1 \pmod 8$, and conequentialy for all powers of $2 > 4$.