4.E: Exercises
( \newcommand{\kernel}{\mathrm{null}\,}\)
Exercise \PageIndex{1}:
Find the \gcd of:
1. 10 and 75
2. 48 and 360
3. 9357 and 5864
- Answer
-
Find the lcm of:
1. 10 and 75
2. 48 and 360
3. 9357 and 5864
Exercise \PageIndex{2}:
Using GCD determine how many packages of hotdogs and hotdog buns are needed to have an equal amount if the hotdog package contains 10 hotdogs, and the hotdog bun package contains 12 buns.
Exercise \PageIndex{3}:
Using Euclidean Algorithm, find the gcd of 1716 and 1260, and the LCM of 1716 and 1260.
Exercise \PageIndex{4}:
- Use the Euclidean algorithm to find \gcd (270, 504).. Find integers x and y such that \gcd (270, 504) =270 x+504 y.
- Use the Euclidean algorithm to find \gcd (-270, 504)., Find integers x and y such that \gcd (-270, 504) =-270 x+504 y.
Exercise \PageIndex{5}:
Suppose a and b are relatively prime integers and c is an integer such that a|c and b|c. Prove that ab|c.
Exercise \PageIndex{6}:
Suppose a and b are relatively prime integers and c is an integer such that a|bc. Prove that a|c.
Exercise \PageIndex{7}:
- Let a and b be non-zero integers with least common multiple l. Let m be any common multiple of a and b. Prove that l|m.
- Prove that if a, b and c are natural numbers, \gcd(a, c)=1 and b \mid c, then \gcd(a, b)=1.
- Suppose a and c are relatively prime integers and b is an integer such that b|c. Prove that gcd(a, b)=1.
Exercise \PageIndex{8}:
Prove that for any positive integer k, 7k+5 and 4k+3 are relatively prime.
Exercise \PageIndex{9}:
Let a, b,c and d be non-zero integers. Then determine whether the following statements are true or false. Justify your answers.
1. If \gcd(a,b)= \gcd(a,c), then b=c.
2. If lcm(a,b)= lcm(a,c), then b=c.
3. lcm(\gcd(a,b),c)=\gcd(lcm(a,b),c).
4. If \gcd(a,b)= \gcd(c,d) and lcm(a,b)=lcm(c,d), then a=b and c=d.
5. \gcd(c,a+b)=\gcd(c,a)+gcd(c,b).
6. \gcd(c,ab)=\gcd(c,a) \gcd(c,b).
7. \gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c)).
Exercise \PageIndex{10}:
Let a, b and c be non-zero integers. Prove the following statements:
1. \gcd(a,b)=\gcd(a, b-a)=\gcd(a,a+b)=\gcd(\pm a,\pm b).
2. \gcd(a,b)=\gcd(a,b-ac).
3. \gcd(ac,bc)=\gcd(a,b) |c|
Exercise \PageIndex{11}:
Solve the following linear congruence:
1. 3x \cong 1( \, mod\, 6).
2. 16x \cong 11( \, mod\, 35).
3. 2x \cong 13( \, mod\, 13).