1
$\begingroup$

I need help solving for $x$ on the following congruence

$x^{49943} \equiv 10855$ mod ($63571$). I started computing $\phi (63571) = 63000$, where $\phi$ is the Euler Phi function. Next, we solve for the variables $u$ and $v$ in the following equation:

$$ku - \phi(m)v = 1$$

Here, $k = 49943$ and $\phi(m) = 63000.$ Computing $gcd(k,\phi(m)) = 1$ and when I solved for $u$ and $v$ via Euclidian algorithm, I got $u = 62807$ and $v = 49790$. To solve for $x$, I need to solve for

$$x = 10855^{62807} mod (63571)$$

Assuming this is correct so far, I have done the method of successive squaring and have noticed that my answer is $0$, which is wrong because $0 \not \equiv 10855$ (mod $63571$). Am I doing this correctly? Any suggestions would be highly appreciated.

$\endgroup$
4
  • $\begingroup$ The reason why I got this answer is because I plugged in all of the numbers on this calculator. $\endgroup$ Apr 3, 2018 at 3:36
  • $\begingroup$ That calculator has the right idea, but is rubbish in the combination stage. It should not go up to that whatever times $10^{49}$. There must have been an overflow there somewhere, and it could no longer cope with exact integer arithmetic. It should have continued to reduce those products modulo $63571$ after every factor. Mathematica gives $$10855^{62807}\equiv42678\pmod{63571},$$ and also confirms that this is a solution to the original congruence. $\endgroup$ Apr 3, 2018 at 5:35
  • 1
    $\begingroup$ +1 for getting started in the right direction and giving the link to the source of your confusion. The problem was not with your understanding but rather with that shabby web calculator :-) $\endgroup$ Apr 3, 2018 at 8:10
  • $\begingroup$ Ah so it was not my work that was wrong after all, it was the calculator that caused the overflow! Appreciate the clarification you gave below. Hopefully, others won't make the same mistake as I did in the future. $\endgroup$ Apr 4, 2018 at 0:14

1 Answer 1

0
$\begingroup$

The problem with that web-calculator is that while it does the modular squaring part (of square-and-multiply) all right, it fails in the multiply part. Apparently the programmer forgot to do those multiplication one at a time, and lazily only tested it with inputs, where this did not result in integer arithmetic overflows, leading to inability to correctly calculate the final remainder.

You can get away with somewhat smaller numbers (still too large for pencil&paper calculations) if you use the Chinese Remainder Theorem. Your modulus factors as $$63571=151\cdot421,$$ so it suffices to calculate the remainder of $10855^{62807}$ modulo both $151$ and $421$.

Modulo the prime $151$ we need that $62807\equiv107\pmod{150}$, and $10855\equiv134\pmod{151}$. Therefore $$ 10855^{62807}\equiv 134^{107}\equiv 96\pmod{151}. $$ I didn't check, but there is some hope that your web calculator can manage this exponent with a lower number of bits.

Similarly modulo the prime $421$ we have $10855\equiv330$ and at the exponent we have $62807\equiv227\pmod{420}$. Therefore $$ 10855^{62807}\equiv 330^{227}\equiv 157\pmod{421}. $$ So, by CRT, the answer is the unique residue class $x$ such that $x\equiv 157\pmod{421}$ and $x\equiv 96\pmod{151}$.

A run of the extended Euclidean algorithm gives that $$1=33\cdot421-92\cdot151.$$ Therefore $$ u=33\cdot421=13893\equiv1\pmod{151} $$ and obviously $u\equiv0\pmod{421}$. Similarly $$ v=-92\cdot151=-13892\equiv1\pmod{421} $$ and also $v\equiv0\pmod{151}$. Therefore $$ x=96u+157v=-847316 $$ has the correct remainders, $96$ and $157$, modulo $151$ and $421$ respectively. This means that the answer is $$ x=-847316\equiv42678\pmod{63571} $$ agreeing with what Mathematica gave for the remainder of $10855^{62807}$ (see my comment under the question).

$\endgroup$
1
  • $\begingroup$ Making this CW, because I don't want any rep points for this. The theory has been explained many times on our site. See this umbrella thread and the scores of questions linked to it. $\endgroup$ Apr 3, 2018 at 8:07

You must log in to answer this question.

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