Die Hard #02

Number Theory Level 4

Find the remainder when $19^{92}$ is divided by 92.

The answer is 49.

4 solutions

Discussions for this problem are now closed

Alexandre Miquilino
Mar 5, 2015

Okay, to solve this we use Euler's Theorem. According to it, if two numbers $a$ and $n$ are coprime, then $a^{\phi(n)} \equiv 1 \pmod{n}$ , where $\phi(n)$ is Euler's totient function.

Since 19 and 92 are coprime, then it follows that:

$19^{\phi(92)} \equiv 1 \pmod{92}$ .

$\phi(92) = 44$ , thus: $19^{44} \equiv 1 \pmod{92}$ .

Then: $19^{92} \equiv 19^{44}*19^{44}*19^{4} \equiv 1*1*19^{4} \equiv 19^{4} \pmod{92}$

$19^4 = 130321$ , and thus $19^{92} \equiv 130321 \pmod{92} \rightarrow 19^{92} \equiv 49 \pmod{92}$ .

Moderator note:

It would easier to show that $19^4 = (19^2)^2 \equiv (-7)^2 \equiv 49$ rather than calculating the value of $19^4$ itself.

Could you please explain me how 130321 equals 49 mod 92 ?

Radhika Nair - 6 years, 3 months ago

One can do this as well: $19^4(\mod {92})=361^2 =(\mod {92}) (-7)^2(\mod {92})=49(\mod {92})$

Vijaysekhar Chellaboina - 6 years, 3 months ago

Long division. Seriously, just do it.

(Alternatively, notice that $130321 = 1416*92 + 49$ , which is the result you should derive from doing the division by hand)

Alexandre Miquilino - 6 years, 3 months ago

how can u solve the theta(92) = 44 in a fastest way..?? tnx :D

Ojna Eugitaraba - 6 years, 3 months ago

@Ojna Eugitaraba – Well, there is a somewhat easy way to do this if you can factor the number in an easy way; Euler has a formula for his phi function that is the following:

$\phi(n) = n*\displaystyle \prod_{p|n} (1 - \frac{1}{p})$

What you're reading above is this: "The totient function of $n$ equals $n$ times the product of all numbers of the form $1 - \frac{1}{p}$ such that $p$ is a prime factor of $n$ ."

Now, when $n = 92$ , we can factor it as: $n = 2^{2}*23$ . Thus, we can write: $\phi(92) = 92*(1 - \frac{1}{2})(1 - \frac{1}{23}) = 92*(\frac{1}{2})*(\frac{22}{23}) = 2*22 = 44$

Alexandre Miquilino - 6 years, 3 months ago

Worranat Pakornrat
Mar 5, 2015

19^2 = (92*4 - 7)

19^92 = (92*4 - 7)^46

When divided by 92, we'll only have 7^46 left.

So 19^92 = 7^46 (mod 92).

7^4 = 9 (mod 92), and (7^2) (9^2) = 13 (mod 92) and 13 (9^3) = 1 (mod 92).

So (7^2) (7^8) = 7^10 = 13 (mod 92) and (7^10) (7^12) = 7^22 = 1 (mod 92).

So 19^92 = (7^44) (7^2) = (1) (49) = 49 (mod 92).

Moderator note:

It would be easier to use modular arithmetic on this very step: $19^{92} = 7^{46} \bmod{92} \equiv 7^{46 \bmod{\phi{(92)}}} = 7^{46 \bmod {44}} = 7^2 = 49$

Anna Anant
Mar 5, 2015

The remainder is 49. Here's why: 19^4=(92 1416+49) So then we can factor out 19^4 from 19^92 so (19^4)(19^88)/92 --> (92 1416+49)(19^88)/92

--->(1416+49/92)(19^88)---->(19^88)(1416)+(19^88)(49/92)

again we factor out 19^4 from the second term and regroup --->(19^88)(1416)+((19^4)/92)(19^84)(49)

--->(19^88)(1416)+(1416+49/92)(19^84)(49)

again we factor and regroup --->(19^88)(1416)+(1416(19^84)(49))+(49(19^80)(19^4)(49/92))

At every step in this process, the last term will be factorable by (19^4)/92, which is (1416 + 49/92), until the only term left is (19^4)/92, which, because it is of the form (92*1416 + 49)/92, has a remainder of 49.

This was not particularly fun, and I'm sure there's a more concise solution.

Moderator note:

Applying the exponentiation properties of modular arithmetic greatly speeds up the process. What you did is analogous of manually adding the same number over and over again without using multiplication.

Gamal Sultan
Mar 4, 2015

92 = (2^2)(23^1)

P(92) = (92)(1 - 1/2)(1 - 1/23) = 44

19^92 = 19^(88 + 4) = 19^4 (mod 92) =

(19^2)(19^2) = (361)(361) = (-7)(-7) = 49 (mod 92)

Moderator note:

Since you're not using $\LaTeX$ , you should mention that P(x) is the Euler totient function of $x$ . And you should mention that your sum of your equal signs are actually equivalent signs: $\equiv$ .

how is 19^(88+4) = 19^4(mod 92)

Pavan Kumar - 6 years, 3 months ago

Die Hard #02

The answer is 49.

4 solutions

Discussions for this problem are now closed

Moderator note:

Moderator note:

Moderator note:

Moderator note:

0 pending reports