What's the quickest way to solve $3^i \equiv 1 \mod 28$ Kind of leading on from my other question, how would I solve for $i$? Or how would I check that it is possible to have such an $i$?
First I had to check for all $2^i$ and clearly this doesn't happen as all $2^i$ are even and so I will just get even $x's$ such that $2^i \equiv x \mod 28$. So the next one I go onto is $3$.
Now how do I go about doing this? 
 A: To solve $a^i \equiv 1 \pmod{n}$, first note that we must have $\gcd(a,n) = 1$ in order to get a positive (non-zero) integer solution. Like you realized, since $\gcd(2, 28)=2$, thus $2^i$ will always be a multiple of $2$, and hence cannot be of the from $28k+1$.
Given that condition, such an $i$ always exists, by Euler's theorem, which states that $ a^{\phi(n)} \equiv 1 \pmod{n}$. The solution, is known as the order. I.e. the smallest positive integer such that $3^k \equiv 1 \pmod{28}$ is called the order of 3 modulo 28.
In this case, we calculate that $ \phi(28) = 28 \times \frac {1}{2} \times \frac {6}{7} = 12$, and so we know that $3^{12} \equiv 1 \pmod{28}$. From here, we only need to check the factors of 12, which are 1, 2, 3, 4, 6, 12.
$3^1 \equiv 3, 3^2 \equiv 9, 3^3\equiv 27 \equiv -1, 3^4 \equiv -3, 3^6 \equiv (-1)^2 \equiv 1 \pmod{28}$. Hence, the order of 3 modulo 28 is 6.
A: $$3^1=3\pmod{28}$$
$$3^2=9\pmod{28}$$
$$3^3=27=-1\pmod{28}$$
$$3^4=3\cdot3^3=-3=25\pmod{28}$$
$$3^5=3^2\cdot3^3=-9=19\pmod{28}$$
$$3^6=3^3\cdot3^3=1\pmod{28}\,\,\ldots\text{etc}$$
A: If you know the Chinese Remainder Theorem, then you see that you can check this separately mod $4$ and mod $7$.  Already $3^2 \equiv 1 \bmod 4,$ and so you
are left to finding the smallest power of $3$ that is $1 \bmod 7$.  By Euler it is a factor of $7- 1,$ i.e. of $6$, and one easily rules out $1,2,$ and $3$.  Thus
$i = 6$ is your answer.  

In this case there is not much difference between this approach and applying
Euler's theorem directly to $28$, since all the numbers involved are small.  But 
in general, if we have $N = mn$ with $m$ and $n$ coprime, then this method
means you only have to compute congruences mod $m$ and $n$, which might be quite a bit easier than working directly mod $N$.  
Also, this method shows that the value of $i$ has to be a factor of the lcm of $\varphi(m)$ and $\varphi(n)$,
whereas applying Euler directly mod $N$, we only get that the value of $i$ is a factor of $\varphi(N) = \varphi(m)\varphi(n)$.
(E.g. since $\varphi(4) = 2$ and $\varphi(7) = 6$, we saw immediately that $i$ would be a factor of $6$, whereas since $\varphi(28) = 12$, applying Euler directly mod $28$ just gives that $i$ is a factor of $12$.)
A: Carmichael Function is more useful than Totient Function, while dealing with composite numbers like $28$.
For
 $\phi(28)=\phi(7)\cdot\phi(4)=6\cdot2=12\implies 3^{12}\equiv1\pmod{28}$
$\lambda(28)=lcm(\lambda(7),\lambda(4))=lcm(6,2)=6\implies 3^6\equiv1\pmod{28}$
So, if $ord_{28}3=d,d\mid 6\implies d $ can be $1,2,3$ or $6$
$3^1=3\not\equiv 1\pmod{28},3^2=9\not\equiv 1\pmod{28},3^3=27\not\equiv 1\pmod{28}\implies ord_{28}3=6$
