# 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?

-
The quickest way I know of to solve that type of relation is to type it in to Wolfram Alpha. I know that's probably not what you're looking for, but it's a way to check your work... :) –  anorton Jan 11 '13 at 1:15
@anorton I disagree. The quickest way is to compute in one's head $3^3=27=-1\pmod{28}$, hence $3^6=1\pmod{28}$, and to convince oneself that neither $3^1$ nor $3^2$ is $1\pmod{28}$. Hence solutions $6\mathbb N$. –  Did Jan 11 '13 at 8:36
@did Actually, I like your way better than mine... :) That's a good explanation... –  anorton Jan 11 '13 at 13:11

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.

-

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$

-

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

-

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

-
Note btw that once you get $3^{3}\equiv -1\pmod{28}$, you know that $3^{3+1}=3^3\times 3\equiv -1\times 3\pmod{28}\equiv-3\pmod{28}\equiv 25\pmod{28}$, $3^{3+2}\equiv -9\pmod{28}$, etc. And in particular: $3^{2\times 3}\equiv -1\times -1 \equiv 1\pmod{28}$. –  Alexander Gruber Jan 11 '13 at 1:29