Reference no: EM13757755

1) [15 points] Use the Extended Euclidean Algorithm to write the GCD of 1183 and 826 as a linear combination of themselves. Show the computations explicitly! [Hint: You should get 7 for the GCD!]
2) [13 points] Compute the LCD of 1183 and 826 [the same numbers above!].
3) [15 points] Find the remainder of the division of 94821532 when divided by 5 [i.e., what is 94821532
congruent to modulo 5]. Show your computations explicitly!
4) [15 points] Give the set of all solutions of the system
4x ≡ 5 (mod 15)
5x ≡ 22 (mod 33)
[Hint: The system does have solution(s)!]
5) [12 points] Suppose that
m = 2a
· 3
2
· 5
b
· 7
3
,
n = 25
· 3
c
· 5
4
· 7
d
,
gcd(m, n) = 25
· 3
2
· 5 · 7
2
,
lcm(n, m) = 27
· 3
2
· 5
4
· 7
3
.
Find a, b, c and d.
6) [15 points] Let a, b and c be positive integers and suppose that there are r, s, t ∈ Z such that
ra + sb + tb = 1.
Prove that gcd(a, b, c) = 1.
7) [15 points] Let p be a prime. Prove that for any integer a such that p - a, the equation
x
p-1 - x + a = 0 never has an integral [i.e., in Z] solution.
[Hint: As I've mentioned before, if an equation has an integral solution, it has a solution modulo
any m.]