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$
6
  • $\begingroup$ Can you elaborate on what your question is? $\endgroup$
    – abiessu
    Commented Feb 18, 2016 at 23:01
  • $\begingroup$ Find integers $k$ such that $5^k\equiv 97\mod(101)$ $\endgroup$
    – user123456789
    Commented Feb 18, 2016 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
    Commented Feb 18, 2016 at 23:04
  • $\begingroup$ Oh sorry, since the numbers are so big, the calculator approached the values of division. $\endgroup$
    – user123456789
    Commented Feb 18, 2016 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
    Commented Feb 19, 2016 at 0:49

3 Answers 3

Reset to default
3
$\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$
1
  • $\begingroup$ Oh. Damn typo. I meant 97; not 1 (of course) $\endgroup$
    – fleablood
    Commented Feb 20, 2016 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$
3
  • $\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
    Commented Feb 19, 2016 at 0:21
  • 1
    $\begingroup$ How do you figure 100 is the "LEAST" such power? It isn't. 25 is. $\endgroup$
    – fleablood
    Commented Feb 19, 2016 at 0:30
  • $\begingroup$ thanks for the catch. I'll fix $\endgroup$
    – Bobby Grizzard
    Commented Feb 19, 2016 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$
2
  • 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
    Commented Feb 20, 2016 at 16:48
  • $\begingroup$ Thanks. I made the correction. $\endgroup$
    – Frank Hubeny
    Commented Feb 20, 2016 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .