1

Evaluating the remainder of $652^{679} : 851$

I'm having trouble solving this problem, specially because I saw congruence properties a long time ago, but this is what I tried:

$652^{679}={652^{7}}^{97} $, but $652^7$ isn't congruent to $851$.

I can't use F.L.T. since $679$ isn't prime nor "prime minus one".

$652^{97}$ is congruent to $652 \mod 97$, by F.L.T.

$652^{7}$ is congruent to $652 \mod 7$, by F.L.T.

But I can't get any further. I believe I could use Chinese Remainder Theorem, but It isn't clear to me what is the $x$ of it in my case.

Thanks.

  • 3
    $851=23\times37$ (in case you find that helpful) – Joffan May 30 '16 at 21:10
  • 2
    679 doesn't have to be prime or prime - 1. 679 can be anything. $\phi(851) = \phi(2337) = 2236$ (thanks Joffan) and 851 and 652 are hopefully relatively prime so $652^{679} \equiv 652^{679 - k2236}\mod 851$. – fleablood May 30 '16 at 21:28

2 Answers2

2

$851=23 \times 37$, and you notice by brute forcing that $652^{11} = 1 \pmod{23}$ and $652^{12} = 1 \pmod{37}$. So : $$652^{679}=652^8 \pmod{23}=4 \pmod{23}$$ $$652^{679}=652^7 \pmod{37}=14 \pmod{37}$$

Now you can apply the Chinese Reminder Theorem.

$652^{679}=14 \pmod{37} \Rightarrow 652^{679}=14+37k=4 \pmod{23} \Rightarrow 14k=13 \pmod{23}$

Finally you need to compute the inverse of $14$ in $\mathbb{Z}_{23}$. With the extended GCD algorithm, we find $(14)^{-1}=5 \pmod{23}$. So $k=5 \times 13 \pmod{23}=19\pmod{23}$. So $k=23l+19$.

Finally $652^{679} =14+37(23l+19)=14+703+851l$.

So $652^{679} = 717\pmod{ 851}$.

Bérénice
  • 9,367
  • By brute forcing you mean use Euler-Fermat equation, right? I understood the equations before "So: ". After it i don't see why the exponents are $8$ and $7$ –  May 30 '16 at 21:30
  • No I just compute by hand : i notice first that $652=8 \pmod{23}\neq 1$, then I do $8^2 \pmod{23} \neq 1$ and then $8^3$ and so on until I reach $1$ – Bérénice May 30 '16 at 21:34
  • 1
    If you want to allow FLT a foot in the door, that computation is your chance - you know that the order of $8 \bmod 23$ must divide $22$, so you can skip some "impossible" exponents by squaring. So I computed $8^2 (\not \equiv 1), 8^4, 8^5, 8^10, 8^11 (\equiv 1) \pmod 23$. Spreadsheets, of course, make the step-by-step approach easy, but then they can sometimes just give the solution directly anyway. – Joffan May 30 '16 at 22:02
0

Through square and multiply algorithm:

$652^1 = 652 \pmod {851}$

$652^2 = 455 \pmod {851}$

$652^4 = (652^2)^2 = 455^2 = 232 \pmod {851}$

$652^8 = (652^4)^2 = 232^2 = 211 \pmod {851}$

$652^{16} = (652^8)^2 = 211^2 = 269 \pmod {851}$

$652^{32} = (652^{16})^2 = 269^2 = 26 \pmod {851}$

$652^{64} = (652^{32})^2 = 26^2 = 676 \pmod {851}$

$652^{128} = (652^{64})^2 = 676^2 = 840 \pmod {851}$

$652^{256} = (652^{128})^2 = 211^2 = 121 \pmod {851}$

$652^{512} = (652^{256})^2 = 211^2 = 174 \pmod {851}$

Aha! Now we see that $652^{512} \times 652^{128} \times 652^{32} \times 652^4 \times 652^2 \times 652^1 \equiv 652^{679} \pmod {851}$

Therefore $174 \times 840 \times26 \times 232 \times 455 \times 652 \equiv 652^{679} \pmod {851}.$

And then:

$$652^{679} \equiv 717 \pmod {851}$$

anonymous
  • 2,423