# Is this right? (modular arthimetic)

• Jan 15th 2010, 08:29 AM
schteve
Is this right? (modular arthimetic)
Just want some confirmation on what i've done -number theory's my weakest area by far.

1. Calculate 7^23 (mod 10)

7^2 = 289 = 9(mod 10)

so 7^22 = (7^2)^11 = 9 (mod 10)

so 7^23 = 7 x 7^22 = 17 x 9^11 = 9(mod 10)
(note: these are meant to be equivalent rather than equals signs)

2. Solve 8x = 12 (mod 20)

gcd(8,20) = 4
4 divides 12 so there are 3 solutions.
A solution is x = 14 (by observation).
Solutions differ by 20/4 = 5.
So 9 and 4 are other solutions as general solutuons given by x= u - (n/d)t
• Jan 15th 2010, 09:38 AM
Dinkydoe
First:

Observe that:

$\displaystyle 7^2= 49 \equiv 9$ mod 10
$\displaystyle 7^4\equiv 9^2\equiv 1$ mod 10

so we observe that: $\displaystyle 7^{a+4k}\equiv 7^a$mod 10

Thus $\displaystyle 7^{23}\equiv 7^3\cdot 7^{20}\equiv 7^3\equiv 7\cdot 9\equiv 3$mod 10

So you answer is incorrect. And the steps you take don't allways make sense.

2.
$\displaystyle 8x\equiv 12$ mod 20
$\displaystyle 8x-12\equiv 8x+8\equiv 0$ mod 20
$\displaystyle 8(x+1)\equiv 0$ mod 20

Observe that $\displaystyle 8(x+1)\equiv 0$ mod 20 $\displaystyle \Leftrightarrow 5|(x+1)$

Thus:
$\displaystyle x\equiv 4$ mod 20
$\displaystyle x\equiv 9$ mod 20
$\displaystyle x\equiv 14$ mod 20
$\displaystyle x\equiv 19$ mod 20
• Jan 15th 2010, 09:54 AM
abender
$\displaystyle 7^{23} = 7^{2^4+2^2+2^1+2^0} = 7^{2^4} \cdot 7^{2^2} \cdot 7^{2^1} \cdot 7^{2^0} =$ $\displaystyle 7^{(2\cdot2\cdot2\cdot2)} \cdot 7^{(2\cdot2)} \cdot 7^2 \cdot 7 = (((7^2)^2)^2)^2 \cdot (7^2)^2 \cdot 7^2 \cdot 7$

$\displaystyle 7^2 = 49 \equiv = 9\pmod{10}$

Substitute: above into equation $\displaystyle 7^{23} \equiv (((7^2)^2)^2)^2 \cdot (7^2)^2 \cdot 7^2 \cdot 7 \pmod{10}$ gives us

$\displaystyle 7^{23} \equiv ((9^2)^2)^2 \cdot 9^2 \cdot 9 \cdot 7 \pmod{10}$

Do this process again for $\displaystyle 9^2 = 81 \equiv 1 \pmod{10}$. We get:

$\displaystyle 7^{23} \equiv ((1)^2)^2 \cdot 1 \cdot 9 \cdot 7 \pmod{10}$

So finally,

$\displaystyle 7^{23} \equiv 1 \cdot 1 \cdot 9 \cdot 7 \pmod{10} \implies 7^{23} \equiv 63 \pmod{10} \implies 7^{23} \equiv 3 \pmod{10}$

-Andy
• Jan 15th 2010, 09:57 AM
abender
Quote:

Originally Posted by Dinkydoe
First:

Observe that:

$\displaystyle 7^2= 49 \equiv 9$ mod 10
$\displaystyle 7^4\equiv 9^2\equiv 1$ mod 10

so we observe that: $\displaystyle 7^{a+4k}\equiv 7^a$mod 10

Thus $\displaystyle 7^{23}\equiv 7^3\cdot 7^{20}\equiv 7^3\equiv 7\cdot 9\equiv$ 63 mod 10 = 3 mod 10

EDIT: You corrected your typo. So this post is irrelevant.
-Andy
• Jan 15th 2010, 10:01 AM
Dinkydoe
Yep: True,

My answer was correct: It was a typo, as you can see I allready corrected it:

The deduction to the last step was correct: $\displaystyle \equiv 9\cdot 7 = 63 \equiv 3$ mod 10
• Jan 15th 2010, 10:03 AM
abender
Quote:

Originally Posted by Dinkydoe
Yep: True,

My answer was correct: It was a typo, as you can see I allready corrected it:

The deduction to the last step was correct: $\displaystyle \equiv 9\cdot 7 = 63 \equiv 3$ mod 10

My fault. The huge red font was not what I wanted. It looks super-obnoxious. I'm going to scale it down.

-Andy