# Modular Question

• Jun 3rd 2009, 04:48 AM
Joel
Modular Question
Hi again,

I have been able to do mod questions such as:

.45 Ξ 3 (mod 6) and 104 Ξ 2 (mod 6)

45 - 3 = 42
42 / 6 = 7 therefore 45 less 3 (42) is a multiple of 6

104 - 2 = 102
102 / 6 = 17 therefore 104 less 2 (102) is a multiple of 6

I am now asked to do a question with a massive number that a calculator can't do.

Verify 675³⁰⁷ mod 713.

How is this done???

• Jun 3rd 2009, 07:16 AM
Soroban
Hello, Joel!

Quote:

I have been able to do mod questions such as:

Verify: .$\displaystyle 104 \equiv 2\text{ (mod 6)}$

. . $\displaystyle 104 - 2 \:=\: 102$

. . $\displaystyle 102 \div6 \:=\: 17\qquad \text{Therefore: }\:104 - 2\text{ is a multiple of 6}$

I am now asked to do a question with a massive number that a calculator can't do.

. . Verify: .$\displaystyle 675^3 \equiv 29\text{ (mod 713)}$ .[1]

How is this done?

We note that: .$\displaystyle 675 \equiv -38\text{ (mod 713)}$

Substitute into [1]: .$\displaystyle (-38)^3 \equiv 29\text{ (mod 713)} \quad\Rightarrow\quad -54,\!872 \equiv 29\text{ (mod 713)}$

. . $\displaystyle -54,\!872 - 29 \:=\:-54,\!901$

. . $\displaystyle -54,\!901 \div 713 \:=\:-77\qquad\text{Hence: }(-38)^3 - 29\text{ is a multiple of 713.}$

Therefore: .$\displaystyle 675^3 - 29$ is a multiple of 713.

• Jun 3rd 2009, 07:24 AM
Joel
675 to the power of 307 is the question.... how do you get http://www.mathhelpforum.com/math-he...68837702-1.gif .[1] ???
• Jun 3rd 2009, 09:00 AM
aidan
Quote:

Originally Posted by Joel

[snip]
I am now asked to do a question with a massive number that a calculator can't do.

Verify 675³⁰⁷ mod 713.

How is this done???

Quote:

675 to the power of 307 is the question.... how do you get
From where did the 307 arrive?

The question is what is $\displaystyle 675^{307} \, mod \, 713$ ?

This is the method I use:

307 = 256 + 32 + 16 + 3

$\displaystyle 675^{256} \times 675^{32} \times 675^{16} \times 675^3 = 675^{307}$

$\displaystyle 675^2 \equiv 18 \, mod(713)$

$\displaystyle 675^4 \equiv 18^2 \equiv 324 \, mod(713)$

$\displaystyle 675^8 \equiv 18^4 \equiv 324^2 \equiv 165 \, mod(713)$

$\displaystyle 675^{16} \equiv 165^2 \equiv 131 \, mod(713)$
That takes care of 1 of the values.

$\displaystyle 675^{32} \equiv 131^2 \equiv 49 \, mod(713)$
That's another one.

$\displaystyle 675^{64} \equiv 49^2 \equiv 262 \, mod(713)$
$\displaystyle 675^{128} \equiv 262^2 \equiv 196 \, mod(713)$
$\displaystyle 675^{256} \equiv 196^2 \equiv 627 \, mod(713)$
Another one.

And the last one.
$\displaystyle 675^3 \equiv 675^2 \times 675 \equiv 18 \times 675 \equiv 29 \, mod(713)$

summary:

$\displaystyle \left ( 627 \times 49 \times 131 \times 29 \right ) \equiv 3 \, mod(713)$

Thus

$\displaystyle 675^{307} \, \equiv 3 \, mod \,\; 713$