# Find all integers $k$ such that $5^k\equiv 97 \pmod{101}$

Find integers $k$ such that $5^k\equiv 97 \pmod{101}$.

By brutal force, If $k=23$ then $101\vert 5^{23}-97$. Furthermore, by Euler-Fermat theorem, since $gcd(5,101)$ we have, $5^{100}\equiv 1\pmod{101}$, then for integer $r$, $5^{100r}\equiv 1\pmod{101}$, so $5^{100r+23}\equiv 97\pmod{101}$, but I'm not sure if this is true, any other idea of how find all intergers k. Thanks!

• Can you elaborate on what your question is? – abiessu Feb 18 '16 at 23:01
• Find integers $k$ such that $5^k\equiv 97\mod(101)$ – user123456789 Feb 18 '16 at 23:03
• I guess you mean find ALL the integers? Also, are you sure that $101 | 5^{16}-97$? – Bobby Grizzard Feb 18 '16 at 23:04
• Oh sorry, since the numbers are so big, the calculator approached the values of division. – user123456789 Feb 18 '16 at 23:20
• To not use brute force not 97 = -4 and -4*25 = -100 = 1. So $5^{-2} \equiv 97 \mod 101$. (That is $k -2$ where $5^k = 1$.) – fleablood Feb 19 '16 at 0:49

$97 \equiv -4 \mod 101$. $-4 * 25 = -100 \equiv 1 \mod 101$.

So if $5^k \equiv 1 \mod 101$ then $5^{k -2} \equiv 97 \mod 101$.

Now $5^{100} \equiv 1 \mod 101$ as 101 is prime so $\phi (101) = 100$ so $5^{\phi(101)} \equiv 1 \mod 101$.

$5^{100} \equiv 1 \mod 101$. So try $5^{50}$ and $5^{25}$ and we see $5^{25} \equiv 1 \mod 101$. If there is any smaller power so that $5^n \equiv 1 \mod 101$ it would be $5$. But $5^5 \equiv 95 \equiv -6 \mod 101$.

So $5^{25} \equiv 1 \mod 101$ so $5^{25-2} = 5^{23} \equiv 97 \mod 101$.

so $k = 25r + 23$ are all the integers such that $5^k \equiv 97 \mod 101$.

• Oh. Damn typo. I meant 97; not 1 (of course) – fleablood Feb 20 '16 at 16:42

The only such $k$ are $k = 23 + 25n$ for all integers $n$.

Proof: First, check that it works for $k=23.$ Next, suppose $k'$ is another, larger integer that works. Then $5^{k-k'}$ would be 1 modulo 101, but this means that $k-k'$ is a multiple of 25, since 25 is the order of 5 in the group of units modulo 101 (i.e. 25 is the LEAST power $m$ such that $5^m \equiv 1 (\mod 101)$).

• Not entirely true 25, not 100, is the order of 5. $k = 23 + 25n$ or $k = 25n - 2$ work as $5^{25} = 1 \mod 101$. – fleablood Feb 19 '16 at 0:21
• How do you figure 100 is the "LEAST" such power? It isn't. 25 is. – fleablood Feb 19 '16 at 0:30
• thanks for the catch. I'll fix – Bobby Grizzard Feb 19 '16 at 2:25

I may have calculated this incorrectly. Please check. I used a Google sheet with three columns.

The first column, A, contained the integers from 1 to 100 as counters.

The second column, B, contained the formula =mod(B\$1*B1,E\$1) starting with the second row. The cell B\$1 contained 5. I copied this formula for counters in A between 2 and 100. The third column, C, contained a conditional formula to alert me if a solution existed. The formula =if(B1=G\$1,"true","") was copied to all the cells with the value in A between 2 and 100.

The cell E\$1 contained the modulus 101. The cell G\$1 contained the desired residue 97.

By this calculation, there are four solutions modulo 100, namely, k equal 23, 48, 73 and 98. The order of 5 modulo 101 is 25.

• "there are four solutions modulo 101": that should be modulo 100, because $\varphi(101) = 100$ (and so $5^{100}\equiv 1 \bmod 101$). – TonyK Feb 20 '16 at 16:48
• Thanks. I made the correction. – Frank Hubeny Feb 20 '16 at 22:39