.

Printable View

- February 7th 2013, 01:53 AMjackGeeFind (10^5)^101 (mod 21)
.

- February 7th 2013, 11:07 AMSorobanRe: Find (10^5)^101 (mod 21)
Hello, jackGee!

Quote:

We find that:

. .

Therefore: .

n . . . . . . . . . . . . .

n . . . . . . . . . . . . .

. . . . . . . . . . . . . .

- February 7th 2013, 11:32 AMjackGeeRe: Find (10^5)^101 (mod 21)
Is there another way to do this, like using Eulidean algorithm ?

because i cant use a calculator on my tests so for an example theres no way i can find 10^5 mod 21

thanks!!! - February 7th 2013, 12:13 PMebainesRe: Find (10^5)^101 (mod 21)
You can use Soroban's method without needing a calculator. The trick is that if you know the mod(21) value for a certain power of ten, you can easily find mod(21) for the next higher power of ten - just multiply 10 by the remainder and find teh mod(21) value of that. Here you know 1 = 1 (mod 21). Multiply by the remainder of 1 by 10 and you find 10^1 = 10(mod 21). Now multiply th eremainder of 10 by 10 again and you get 10^2 = 16 mod 21. Continue for 10^3: 10 x 16 = 13 (mod 21). For 10^4: 10 x 13 = 4 mod(21). For 10^5: 10x4 = 19 mod(21). Then for 10^6: 190 = 1 mod(21). And then the pattern repeats.

- February 7th 2013, 07:32 PMjohngRe: Find (10^5)^101 (mod 21)
Here's yet another way to cut down on the arithmetic. mod 7 and mod 3. So by the Chinese remainder theorem, mod 21.