4.E: Exercises

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}$:

1. Use the Euclidean algorithm to find $\gcd (270, 504).$. Find integers $x$ and $y$ such that $$\gcd (270, 504) =270 x+504 y.$$
2. 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}$:

1. 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.$
2. Prove that if $a, b$ and $c$ are natural numbers, $\gcd(a, c)=1$ and $b \mid c$, then $\gcd(a, b)=1$.
3. 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).$