# 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: . $104 \equiv 2\text{ (mod 6)}$

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

. . $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: . $675^3 \equiv 29\text{ (mod 713)}$ .[1]

How is this done?

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

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

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

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

Therefore: . $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 $675^{307} \, mod \, 713$ ?

This is the method I use:

307 = 256 + 32 + 16 + 3

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

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

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

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

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

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

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

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

summary:

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

Thus

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