1. ## Modular Arithmetic examples

Just picked out a few examples from a practice exam.

1)Solving the equation az=1 mod m

(a) a=3 m = 10 (ANS = 7)
(b) a=5 m = 18

2)Solve the following congruence, equations for x.(Giving the solution in the form a mod m)

(a) 3x - 1 = 7 mod 10 (ANS = x = 6 mod 10)

Any chance of a step by step explanation on a few of them .

2. Hello,
Originally Posted by Ciachyou
Just picked out a few examples from a practice exam.

1)Solving the equation az=1 mod m

(a) a=3 m = 10 (ANS = 7)
(b) a=5 m = 18
In fact, you're asked to find the inverse of numbers modulo m.

Let's do it for these two, I guess they'll give you quite the general idea. The key is to use the extended Euclidean algorithm (you can look for it in google)

Find z in $\displaystyle 3z \equiv 1 \bmod 10$

You know that since 3 and 10 are coprime, you'll have a remainder 1 while continuing doing the algorithm. And this is why it is useful.

Do the algorithm with 10 and 3 as starting points :
$\displaystyle 10=3 \times 3+1$
Hence $\displaystyle 1=10-3 \times 3$

You can note that $\displaystyle 10-3 \times 3 \equiv -3 \times 3 \bmod 10$ because $\displaystyle 10 \equiv 0 \bmod 10$

So we have $\displaystyle -3 \times 3 \equiv 1 \bmod 10$
$\displaystyle z=-3 \bmod 10$
In general, we want z to be the least positive integer satisfying the condition.

So you can add 10 : $\displaystyle z=7$

For the second one, you're looking for z in $\displaystyle 5z \equiv 1 \bmod 18$
Algorithm for 5 and 18 :
$\displaystyle 18=5 \times 3+3$
My method is to write successively the remainders.
$\displaystyle 3=18-5 \times 3$

Now, do the division for 5 and the new remainder, 3.
$\displaystyle 5=3 \times 1+2$
$\displaystyle \implies 2=5-3$

Division for 3 and the new remainder, 2.
$\displaystyle 3=2+1$
$\displaystyle \implies 1=3-2$

But we saw that $\displaystyle 2=5-3$ :
$\displaystyle \implies 1=3-(5-3)=2 \times 3-5$
$\displaystyle \implies 1=2 \times (18-5 \times 3) -5=18 \times 2-5 \times 6-5=\boxed{18 \times 2-5 \times 7}$

So we have $\displaystyle -5 \times 7 \equiv 1 \bmod 18$

$\displaystyle \implies z \equiv -7 \bmod 18 \equiv 11 \bmod 18$

3. Thanks, that helped me out alot.
Got a b+