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

Printable View

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

Quote:

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

We find that:

. . $\displaystyle \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: .$\displaystyle 10^{505} \;=\;10^{6\cdot84+1}$

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

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

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