1

I would like to understand who it works the modulo with Straightforward method. For example I try to test this: 290 mod 1009 = 257^x mod 1009. Which is the "x"?

 1 attempt --> 1*257 mod 1009 = 257
 2 attempt --> 257*257 mod 1009 = 464
 3 attempt --> 464*257 mod 1009 = 186
 4 attempt --> 186*257 mod 1009 = 379
 5 attempt --> 379*257 mod 1009 = 539
 6 attempt --> 290*257 mod 1009 = 290

Therefore x=6. 290 mod 1009 = 257^6 mod 1009.

I can't understand how in 3 attempt the 464*257=119248 gives the same modulo with 257^3=16974593.

bob
  • 11

1 Answers1

1

$\begin{eqnarray}{\rm {\bf Hint}\!:\ mod}\ 1009\!:\ &&\color{#c00}{257^2}\ \equiv\ \color{#0a0}{464}\\ \Rightarrow 257^3\equiv &&\color{#c00}{257^2}\cdot 257\equiv \color{#0a0}{464}\cdot 257\end{eqnarray}$

where we've substituted the $\rm\color{#c00}{argument}$ of a product by a $\rm\color{#0a0}{congruent\ integer}$, i.e. we used the

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab} $

Bill Dubuque
  • 272,048