5
$\begingroup$

Calculate $142^{381}$ mod $773$ without a calculator .

Attempt:

$$142^{(3\cdot 127)}=142^{381}$$ By try some number's $$142^1\equiv142\pmod{773}$$ $$142^2\equiv66\pmod{773}$$ $$142^3\equiv96\pmod{773}$$

Lets check the gcd between $773,142$ $$\gcd(773,142)$$ $$773=142\cdot 5+63$$ $$142=63\cdot 2+16$$ $$63=16\cdot3+15$$ $$16=15\cdot 1+1$$ $$15=1\cdot15+0$$ $$\gcd(773,142)=1$$ How to find the answer from here ?

$\endgroup$
9
  • 1
    $\begingroup$ Your calculations are not correct. $142^1 \equiv 142, 142^2\equiv 66, 142^3\equiv 96 \pmod{773}$ $\endgroup$ Dec 25, 2020 at 22:10
  • $\begingroup$ @RossMillikan Correct, I edited Thanks for the Correction. $\endgroup$
    – ATB
    Dec 25, 2020 at 22:15
  • $\begingroup$ Ast the end of your question you seem to be assuming $\;773\;$ is prime. Are you given this or have you already proved it? $\endgroup$
    – DonAntonio
    Dec 25, 2020 at 22:20
  • 2
    $\begingroup$ Clarification requested: what is the query's context (i.e. background)? Is this a problem that you made up for yourself, or is this a problem that was assigned to you from a book/class/online-pdf? My first step was to consult my number theory book to confirm that 773 is a prime. Then, I factored $142 = 2 \times 71.$ Then, I considered exploring $(71)^2 \pmod{773}, (71)^3 \pmod{773}, \cdots$ In my opinion, my approach (which might not be the only approach) is not feasible for me without a calculator. $\endgroup$ Dec 25, 2020 at 22:39
  • 1
    $\begingroup$ @TonyK Note that the OP did not outlaw using an abacus. $\endgroup$ Dec 25, 2020 at 22:41

3 Answers 3

1
$\begingroup$

Let

$$ x = 142^{381} \pmod{773}. $$

Since $773$ is prime, by Fermat's little theorem we have

$$ 142^{772} = 1 \pmod{773}. $$

Therefore, either

$$ 142^{386} = 1 \pmod{773} $$

or

$$ 142^{386} = -1 \pmod{773}. $$

We can distinguish the two cases using Euler's criterion. To that end, we need to compute the Legendre symbol

$$ \left(\frac{142}{773}\right) = \left(\frac{71}{773}\right)\left(\frac{2}{773}\right) $$

where we used the fact that Legendre symbol is a completely multiplicative function. Next, we use the law of quadratic reciprocity to find

$$ \left(\frac{71}{773}\right) = \left(\frac{773}{71}\right) = \left(\frac{710 + 63}{71}\right) = \left(\frac{63}{71}\right) $$

and similarly

$$ \left(\frac{63}{71}\right) = -\left(\frac{71}{63}\right) = -\left(\frac{8}{63}\right) = -\left(\frac{2}{63}\right)\left(\frac{2}{63}\right)\left(\frac{2}{63}\right). $$

Substituting, we see that

$$ \left(\frac{142}{773}\right) = -\left(\frac{2}{63}\right)\left(\frac{2}{63}\right)\left(\frac{2}{63}\right)\left(\frac{2}{773}\right). $$

Now, using the property known as the second supplement to the law of quadratic reciprocity

$$ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} $$

we find

$$ \left(\frac{2}{773}\right) = -1 \\ \left(\frac{2}{63}\right) = 1. $$

Therefore,

$$ \left(\frac{142}{773}\right) = 1 $$

and so $142$ is a quadratic residue. Consequently,

$$ 142^{386} = 1 \pmod{773}. $$

Now, substituting $x$ and partial results listed in the question

$$ x \cdot 142^5 = 1 \pmod{773} \\ x \cdot 142^2 \cdot 142^3 = 1 \pmod{773} \\ x \cdot 66 \cdot 96 = 1 \pmod{773} \\ x \cdot 152 = 1 \pmod{773}. $$

Thus, we see that $x$ is the multiplicative inverse of $152$ modulo $773$. We can find it by computing Bézout's coefficients using Euler's algorithm

$$ 152 \cdot 178 + 773 \cdot (-35) = 1 $$

and so we see that

$$ 178 \cdot 152 = 1 \pmod{773}. $$

Therefore,

$$ x = 178 \pmod{773}. $$

$\endgroup$
1
$\begingroup$

Easily we verify $\,773\,$ is prime. So $\!\bmod 773\!:\, $ if $\,142 \equiv a^2\,$ then $142^{386}\equiv a^{772}\equiv 1\,$ by Fermat, so $\,142^{381}\equiv 142^{386} 142^{-5}\equiv (142^{-1})^5.\,$ By here $\,142^{-1}\equiv 7^2\,$ so $\,142\equiv 7^{-2}\,$ is indeed a square, so $\,142^{381}\equiv 49^5\equiv 49(82)^2 \equiv 49(-223)\equiv 178.\,$ Total time: a few minutes by hand.

$\endgroup$
3
  • $\begingroup$ We could also use quadratic reciprocity (Legendre symbol) to check that $142$ is a square $\bmod 773\ \ $ $\endgroup$ Dec 26, 2020 at 0:15
  • $\begingroup$ Did you do $0/773 \equiv 1/142 \equiv -5/63 \equiv 11/16 \equiv -49/(-1)$ (I was too lazy to include the frowns) or something else? Thanks. $\endgroup$
    – Neat Math
    Dec 26, 2020 at 20:46
  • 1
    $\begingroup$ @NeatMath Yes, that's exactly what we get using the fractional extended Euclidean algorithm. $\endgroup$ Dec 26, 2020 at 21:15
0
$\begingroup$

The standard algorithmic solution to the "modular exponentiation" problem is to use "Square and Multiply Algorithm". Let me illustrate:

Suppose you need to calculate $$x^c \bmod n$$

Represent the exponent $c$ in binary:

$$c = \sum_{i=0}^{l-1} c_i 2^i$$ where $c_i$ is $0$ or $1$ and $0 \leq i \leq l-1$

Then use the following algorithm:

SAM (x, c, n){
z = 1

for i = l-1 downto 0 {
   z = z^2 mod n
   if (c_i = 1)
      z = zx mod n
   }

return z
}

Note that there are always $l$ squarings. The number of multiplications is equal to the number of $1$'s in the binary representation of $c$, which is an integer between $0$ and $l$. Thus the total number of modular multiplications is at least $l$ and at most $2l$

I used the above algorithm and found the value $178$

$x = 142, c = 381 = \{101111101\}, n = 773$

Here $l = 9$,

hence the number of squarings $= l = 9$ and

number of multiplications $ = $ number of $1$'s in the binary representation of $381 = 7$

SQUARE: 1
MULTIPLY: 142
SQUARE: 66
SQUARE: 491
MULTIPLY: 152
SQUARE: 687
MULTIPLY: 156
SQUARE: 373
MULTIPLY: 402
SQUARE: 47
MULTIPLY: 490
SQUARE: 470
MULTIPLY: 262
SQUARE: 620
SQUARE: 219
MULTIPLY: 178
===============
FINAL: 178
$\endgroup$
0

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.