# Is this right? (modular arthimetic)

Printable View

• January 15th 2010, 09: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)

MY ANSWER: 7=17 (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)

MY ANSWER:

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
• January 15th 2010, 10:38 AM
Dinkydoe
First:

Observe that:

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

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

Thus $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.
$8x\equiv 12$ mod 20
$8x-12\equiv 8x+8\equiv 0$ mod 20
$8(x+1)\equiv 0$ mod 20

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

Thus:
$x\equiv 4$ mod 20
$x\equiv 9$ mod 20
$x\equiv 14$ mod 20
$x\equiv 19$ mod 20
• January 15th 2010, 10:54 AM
abender
$
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} =$
$
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
$

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

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

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

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

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

So finally,

$
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
• January 15th 2010, 10:57 AM
abender
Quote:

Originally Posted by Dinkydoe
First:

Observe that:

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

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

Thus $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
• January 15th 2010, 11: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: $\equiv 9\cdot 7 = 63 \equiv 3$ mod 10
• January 15th 2010, 11: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: $\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