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

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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.