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