2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Can you elaborate on what your question is? $\endgroup$ – abiessu Feb 18 '16 at 23:01
  • $\begingroup$ Find integers $k$ such that $5^k\equiv 97\mod(101)$ $\endgroup$ – user123456789 Feb 18 '16 at 23:03
  • 1
    $\begingroup$ I guess you mean find ALL the integers? Also, are you sure that $101 | 5^{16}-97$? $\endgroup$ – Bobby Grizzard Feb 18 '16 at 23:04
  • $\begingroup$ Oh sorry, since the numbers are so big, the calculator approached the values of division. $\endgroup$ – user123456789 Feb 18 '16 at 23:20
  • 1
    $\begingroup$ 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$.) $\endgroup$ – fleablood Feb 19 '16 at 0:49
4
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – fleablood Feb 19 '16 at 0:21
  • 1
    $\begingroup$ How do you figure 100 is the "LEAST" such power? It isn't. 25 is. $\endgroup$ – fleablood Feb 19 '16 at 0:30
  • $\begingroup$ thanks for the catch. I'll fix $\endgroup$ – Bobby Grizzard Feb 19 '16 at 2:25
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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