Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

4 Answers 4

up vote 7 down vote accepted

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.

share|improve this answer
add comment

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$

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.