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

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 ?

• Your calculations are not correct. $142^1 \equiv 142, 142^2\equiv 66, 142^3\equiv 96 \pmod{773}$ Dec 25, 2020 at 22:10
• @RossMillikan Correct, I edited Thanks for the Correction.
– ATB
Dec 25, 2020 at 22:15
• Ast the end of your question you seem to be assuming $\;773\;$ is prime. Are you given this or have you already proved it? Dec 25, 2020 at 22:20
• 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. Dec 25, 2020 at 22:39
• @TonyK Note that the OP did not outlaw using an abacus. Dec 25, 2020 at 22:41

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}.$$

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.

• We could also use quadratic reciprocity (Legendre symbol) to check that $142$ is a square $\bmod 773\ \$ Dec 26, 2020 at 0:15
• 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. Dec 26, 2020 at 20:46
• @NeatMath Yes, that's exactly what we get using the fractional extended Euclidean algorithm. Dec 26, 2020 at 21:15

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