Find (10^5)^101 (mod 21)

• Feb 7th 2013, 02:53 AM
jackGee
Find (10^5)^101 (mod 21)
.
• Feb 7th 2013, 12:07 PM
Soroban
Re: Find (10^5)^101 (mod 21)
Hello, jackGee!

Quote:

$\text{Find: }\: (10^5)^{101} \text{ (mod 21)}$

We find that:

. . $\begin{array}{cccc}10^0 &\equiv & 1 & \text{(mod 21)} \\ 10^1 &\equiv& 10 & \text{(mod 21)} \\ 10^2 &\equiv& 16 & \text{(mod 21)} \\ 10^3 &\equiv & 13 & \text{(mod 21)} \\ 10^4 &\equiv& 4 & \text{(mod 21)} \\ 10^5 &\equiv& 19 & \text{(mod 21)} \\ 10^6 &\equiv& 1 & \text{(mod 21)} \end{array}$

Therefore: . $10^{505} \;=\;10^{6\cdot84+1}$

n . . . . . . . . . . . . . $=\;(10^6)^{84}\cdot 10^1$

n . . . . . . . . . . . . . $\equiv\:1^{84}\cdot 10\text{ (mod 21)}$

. . . . . . . . . . . . . . $\equiv\:10\text{ (mod 21)}$
• Feb 7th 2013, 12:32 PM
jackGee
Re: 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!!!
• Feb 7th 2013, 01:13 PM
ebaines
Re: 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.
• Feb 7th 2013, 08:32 PM
johng
Re: Find (10^5)^101 (mod 21)
Here's yet another way to cut down on the arithmetic. $10^{505}=3^{505}=3^{6\cdot 84+1}=3$ mod 7 and $10^{505}=1^{505}=1$ mod 3. So by the Chinese remainder theorem, $10^{505}=10$ mod 21.