Is there a procedure to solve this or is it strictly by trial and error?
$5^x \equiv 5^y \pmod {39}$ where $y > x$.
Thanks.
Is there a procedure to solve this or is it strictly by trial and error?
$5^x \equiv 5^y \pmod {39}$ where $y > x$.
Thanks.
Since the $\gcd(5, 39) = 1$ then $5^{x}$ has a multiplicative inverse $5^{-x}$. Multiplying both sides by the inverse, we get that $5^{y - x} = 1 \pmod{39}$.
By trial and error, we get that the order of $5$ is $4$ (that is $5^4 = 1 \pmod{39}$ and 4 is the smallest positive exponent that gives $1$). Then we know that $4 | y - x$, that is $y = 4 k + x$.
If you are wondering if there is another faster way to get the order of $5$, there is no general (much faster way) known way, see this. There are ways to do it in something like $O(\sqrt{n})$, where n is the mod ($39$ in this case).
We can rewrite your problem as $5^{y-x}=1\bmod 39.$ So we are trying to find the positive integers $k$ such that $5^k=1\bmod{39}$. Since we can find the prime power factorization of $39$ easily, our problem reduces to finding the positive $n$ such that (simultaneously) $5^n=1\bmod 3$ and $5^n=1 \bmod{13}$.
If $p$ is a prime which does not divide $a$, then the smallest positive $d$ such that $a^d=1 \bmod{p}$ is a divisor of $p-1$.
Let $a=5$ and $p=3$. Then $p-1$ has only the divisors $1$ and $2$. Obviously $5^1 \neq 1\bmod{3}$. So the smallest $d$ that works for $p=3$ is $d=2$.
Let $a=5$ and $p=13$. Then $p-1=12$, so our candidates for $d$ are the divisors of $12$. It is easy to check that $1$, $2$, and $3$ don't work. But $4$ does.
Now we want the smallest $d$ that works for both $3$ and $13$. This is the least common multiple of the $d$ that works for $3$ and the $d$ that works for $13$. The least common multiple of $2$ and $4$ is $4$.
We conclude that the least positive $d$ such that $5^d=1\bmod{39}$ is $4$. By a general theorem, the $n$ such that $5^n=1\bmod{39}$ are the multiples of $4$. So we can write $n=4k$, where $n$ ranges over the positive integers.
Thus in the original problem, the pairs $(x,y)$ that satisfy your condition are all pairs $(x,x+4k)$. You say that you want $x\ge 1$, so the pairs are all pairs $(x,y)$ where $1\le x$ and $y-x$ is a positive multiple of $4$.
Remark: If instead of working with the small number $39$, we work with a huge number $m$, then the prime power factorization of $m$ can be computationally very difficult.
Even after we have factored $m$, things can be computationally very unpleasant, even in the simplest case where $m$ is prime, or a product of two primes. There are algorithms that are much better than the crude try everything approach, but still, they are not fast enough to deal with $m$ if it is $150$ digits long.
For small $m$, like our $39$, or even modestly large $m$, say of size less than $10^6$, there are programs that give virtually instantaneous answers.
Hint: since $39 = 3\cdot 13$ we can compute the order of $5\ ({\rm mod}\ 39)$ from its order mod $3$ and mod $13$.
First, mod $13\!:\ 5^2\equiv -1\ \Rightarrow\ 5^4\equiv 1;\ \ $ Second, mod $3\!:\ 5\equiv -1\ \Rightarrow\ 5^2\equiv 1\ \Rightarrow\ 5^4\equiv 1 $.
Thus $\:3,13\ |\ 5^4-1\ \Rightarrow\ {\rm lcm}(3,13)\ |\ 5^4-1,\:$ i.e. $\:39\ |\ 5^4-1,\:$ i.e. $\:5^4\equiv 1\pmod {39}$