If $3^x \bmod 7 = 5$, what is $x$ and how?

Question

I am an amateur java programmer who is stuck on this problem:

$$3^x \bmod 7 = 5$$

then what is $x$ and how? If you can even explain the method for how to arrive at the solution, then it will be very helpful.

Answer 1

There are very few values in $\mod 7$, which are $0,1,2,3,4,5,6$. Look now at the values of $3^x$:

$$3,9,27,81,243,729,\dots$$ After modding out you get $$3,2,6,5,4,1,\dots$$

To mod out, we subtract $7$ untill we get a number $<7$:

$$9-7=2$$ $$27-7\times 3=6$$ $$81-7\times 10=11\;,\; 11-7=4$$ $$243-7\times 30=33\;,\; 33-7\times 4=5$$ $$729-7\times 100=29\;,\; 29-7\times 4=1$$

Since after getting up to $x=6$ we exhausted all elements, the sequence will repeat: that is, for $x=1,2,\dots$ $$3^x\mod 7$$ is $$3,2,6,5,4,1,3,2,6,5,4,1,\dots$$

Answer 2

Given your java background, I'll include an explanation in terms of integer division and the modulus operator in java, as well.

The least positive integer solution is $$x = 5:\; 3^5 = 243 = \underbrace{{\bf}7}_{mod}\times \color{blue}{\bf 34} + \color{red}{\bf 5}$$

where $\color{blue}{\bf 34}$ corresponds to the value of integer division $243/7 = 34$, (the floor of the quotient when dividing by $7),\;$ and $\color{red}{\bf 5}$ corresponds to the value resulting from modulus operation $\;243\; \% \;7 = 5\;$ (the remainder when dividing $243$ by $7$).

Hence, $3^5 \equiv 5 \pmod 7 \iff 7 \mid (3^5 - 5):\;\;$ $7$ divides $3^5 - 5$

There aren't many to examine.

I simply listed $3^1, 3^2, 3^3...$ and found $3^5: x = 5$ to be the least positive value solving the congruence, modulo $7$.

To determine for any given value $x$, whether $3^x$ is equivalent to $5$, mod $7:\;$ divide$3^x$ by the modulus: 7, and determine the remainder $\;3^x \;\% \;7$. $$3^x \pmod 7 = 5 \iff 3^x \;\%\; 7 = 5$$

Answer 3

the type of x is not clear. I mean is it real or integer? but I assume that it is integer the following code in c# will calculate x and the first value of x is 5. if you remove the end_condition , then you could see the next values of x which are 5, 11, 17, 23, 29, 44, and so on...

bool end_condition = false;
int x = 1;
while (!end_condition)
{
     if ((Math.Pow(3, x)-5) % 7 == 0)
     {
         Console.WriteLine(x);
         end_condition = true;
     }
     else                                    
         x++;                
}

Answer 4

This is a famous and important problem, called the [Discrete Logarithm Problem.] (http://en.wikipedia.org/wiki/Discrete_logarithm) It has a number of applications in cryptograpjy. We have provided the name and link so that you can, if you wish, search for additional information. Be warned that much of the work is difficult, and requires considerable number-theoretic background.

A general version of the problem is, given the numbers $a$, $b$, and the prime $p$, to find $x$ such that $a^x\equiv b\pmod{p}$.

Such an $x$ need not exist. Even for very large $p$, there are efficient ways, given $a$, $b$, and $p$, to determine whether a solution $x$ exists.

However, actually finding $x$ is another matter. Many algorithms have been produced. The above link provides links to some of them. However, for huge $p$, finding $x$, even with state of the art procedures, can be very slow. Computing $b$ given $a$ and $p$ is relatively cheap, but travelling the other way, from $b$ to $x$, appears to be computationally difficult. That accounts for the importance of the discrete logarithm problem in cryptography.

For small primes, a brute force search works well. If you will do it by hand, it is useful to reduce modulo $p$ on the fly, to keep numbers small.

For your example, we have, modulo $7$, that $$3^0\equiv 1,\quad 3^1\equiv 3,\quad 3^2\equiv 9\equiv 2,\quad 3^3\equiv 6,\quad 3^4\equiv 18\equiv 4,\quad 3^5\equiv 12\equiv 5.$$ Bingo!