Question

I would like to know if my answers are correct. I also need help solving some exercises the right way.
(a) Explain why [13] is invertible in
Z50.

Ans: it's invertible because
there's some [t]E Z50 such that
[13][t]=1

(b) Use the usual algorithm to find
[13]^(-1)and give your anwer
mod50.

Ans: [13]^(-1) = ? mod50

I wasn't sure how to use the usual
algorithm to solve this so I
used the matrix form, hopefully I
did it right. But I know that
I won't get full credit for it.
So, I would like to know the
right way of doing it.

__ __ __ __
| 1 0 | 50 | ~ | 1 -3 | 11 | ~
| 0 1 | 13 | | 0 1 | 13 |
-- -- -- --
__ __ ___ ___
| 1 -3 | 11 | ~| 6 -23 | -1 |
| -1 4 | 2 | | -1 4 | 2 |
-- -- -- --

1=6[50] -23[13] ==> [1]= -23[13]
==> [13]^(-1) = [-23]
(Can i just leave it like that or do I
have to continue?)

long division :
2 |So, 23+ remainder =
____ | 23 + 4= 27
23 | 50 |Therefore.
46 |
---- | [t]=[27] mod 50
4 | ===> [13][27]=1


(c) Use your answer in part (b) to solve the congruence 13x= 20mod 50.
and give your answer in mod50.

Ans: I wasn't sure how to solve it, so I did it the long way, one by one.
a =bmodn
13X=20mod 50 ==> 50 | 13x- 20
When x=40 ==>
50 | 13(40)-20 => it has
remainder 20 when
I do long division.
But I would like to know how to do it the right way.

Answer 1

The matrix method is the most efficcient way.

-23 is the same as 27 mod 50.

13x= 20 (everything = mod 50)---->

x = 13^(-1)*20 = 27*20 = (25 + 2)*20 = 40