Content deleted Content added
mNo edit summary |
|||
Line 13:
& = & (g^{\phi(p)/p_1})^{b_1} \pmod{p}
\end{matrix}
</math> (using [[Euler's theorem]])</center><br>Note that if <math>g^{\phi(p)/p_1} = 1 \pmod{p}</math> then the order of ''g'' is less than ø(''p'') and <math>e^{\phi(p)/p_1} \mod p</math> must be 1 for a solution to exist. In this case there will be more than one solution for ''x'' less than ø(''p''), but since we are not looking for the whole set, we can require that ''b''<sub>1</sub>=0.<br><br>The same operation is now performed for ''p<sub>2</sub>'' up to ''p<sub>n</sub>''.<br><br>A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p<sub>i</sub>'' for the ''k+1''-th time. Then we already know ''c<sub>i</sub>'' in the equation ''x = a<sub>i</sub> p<sub>i</sub><sup>k+1</sup> + b<sub>i</sub> p<sub>i</sub><sup>k</sup>+c<sub>i</sub>'', and we find ''b<sub>i</sub>'' the same way as before.
#We end up with enough simultaneous congruencies so that ''x'' can be solved using the [[Chinese remainder theorem]].
| |||