2
$\begingroup$

I want to calculate

$$119^{7} \text{mod}~ 143$$

I got this one step from a solution sheet, which I don't understand: $$119^{7} ~\text{mod}~ 143 = (-12 * 2)^{7} ~\text{mod}~143$$ Still getting this, because $-24$ is the same like 119. But now the strange thing: $$(-12 * 2)^{7} ~\text{mod}~143 = -12 * 128 ~\text{mod}~143$$ How does this work? I mean I understand, that $2^{7}$ is $128$, but why is there just $-12$ instead of $-12^{7}$?

It ends with this (which I understand): $$= 12 * 15 ~\text{mod}~143 = 180 ~\text{mod}~ 143 = 37$$

Can someone explain me this one 'strange' step for me? Thank you so much.

| cite | improve this question | | | | |
$\endgroup$
3
$\begingroup$

Note that $$(-12)^7 \equiv ((-12)^2)^3(-12) \equiv 1^3(-12) \equiv -12 \pmod {143}$$ since $12^2 = 144$.

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

$$-12\equiv-1\pmod{11}$$ so $$(-12)^7\equiv-1\equiv-12\pmod{13}.$$ $$-12\equiv1\pmod{13}$$ so $$(-12)^7\equiv1\equiv-12\pmod{13}.$$ By the Chinese Remainder Theorem, $$(-12)^7\equiv-12\pmod{143}.$$

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

Somehow the text is assuming it must be obvious that $(-12)^7 \equiv -12 \mod 143$. So we should ask ourselves why that would be.

$143 = 11*13 = (12-1)*(12 + 1) = 12^2 -1 = 144$. Therefore $(\pm 12)^2 \equiv 1 \mod 143$ and $(-12)^7 = -12(-12)^6 \equiv -12 \mod 143$.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.