Solve the following equations for x and y or show that no solution exists 1. 9x
ID: 640380 • Letter: S
Question
Solve the following equations for x and y or show that no solution exists
1. 9x + 80 ? 2 (mod 81)
2.5x + 13 ? 11 (mod 504)
3.The system of simultaneous equations 30x + 2y? 0 (mod 37) and y ?4 + 13x (mod 37)
4.(a)if gcd(m, x) = 1 then x has a (unique) inverse modulo m. State the converse of this proposition: Prove the converse.
(b)Which of the integers modulo 12 has an inverse? For those that have an inverse, specify it
(c)Use the extended-gcd algorithm to express gcd(100001, 1001) as a linear combination of 100001 and 1001. Show clearly the sequence of recursive calls and values returned by the algorithm.
Explanation / Answer
1)
1. 9x + 80 ? 2 (mod 81)
rhs gives always 2...where as lhs contains minimum 8 or max>80............so this equation fails
2.5x + 13 ? 11 (mod 504)
same as above explaination
3)
Suppose x has an inverse modulo m. Then for some integer y we have xy?1(modm). Thus xy?1=qm for some integer q.
Now we show that gcd(x,m)=1. This follows from the fact that (m)(?q)+(x)(y)=1. If further details is needed, suppose that d divides x and m. Then from (m)(?q)+(x)(y)=1 we conclude that d divides 1. It follows that no d>1 can be a common divisor of x and m.