Find different negative integers $a$ and $b$ which satisfy the following:
(a) $\gcd (a, b) = 5$
(b) $\gcd (a, b) = 100$
(c) $\gcd (a, b) = 169$
We can do this exercise by using the negation of the gcd as one of the negative integers, and then for the second we can multiply that negative integer by a prime number such that is not a factor of it.
(a) $\gcd (-5, -10) = 5$
(b) $\gcd (-100, -200) = 100$
(c) $\gcd (-169, -338) = 169$
Suppose $198 \mid 5x$. Show that $198 \mid x$.
Euclid's Lemma says that if $a \mid (bc)$ with $\gcd (a, b) = 1$ then $a \mid c$.
Here $\gcd(198,5)=1$ so by Euclid's Lemma $198 \mid x$.
Another way to look at this is that 5 is prime and only has factors 1 and 5. Therefore 198 can't be a factor of 5, so must be a factor of $x$.
Explain why there are no positive integer solutions to $5x + 6y= 1$.
[Hint: Sketch a graph.]
A graph of $5x+6y$ shows that in the quadrant of positive solutions, marked green, there are no integer solution.
The graph is here.
Show that there is no integer solution to the linear equation $20x + 28y= 2$.
The smallest positive integer value of $20x + 28y$ is $\gcd(20,28)$, which is 4.
Therefore the integer values of $20x + 28y$ cannot be 2, so the equation has no integer solutions.
Given that $gcd (a, b) = 1$ and integers $x_0$ and $y_0$ are solutions to $ax + by= 1$, determine an integer solution to $ax + by= c$ where $c$ is an integer.
We're given
$$ a(x_0) + b(y_0) = 1 $$
Multiplying though by $c$ we have
$$ a(cx_0) + b(cy_0) = c $$
Here $cx_0$ and $cy_0$ are integers, because $c, x_0, y_0$ are integers.
So $x=cx_0, y=cy_0$ is an integer solution of $ax + by= c$.
Note: We don't make use of $\gcd(a,b)=1$.
Find integers $x$ and $y$ in each of the following cases:
(i) $314x + 785y= 157$
(ii) $314x + 785y= 314$
(iii) $314x + 785y= −1570$
(i) The gcd of 214 and 785 is conveniently 157. This means we can divide through by 157 to give
$ 2x + 5y = 1$
By inspection we have $x=3, y=-1$.
(ii) 314 is $2 \times \gcd(314,785)$.
$ 314x + 785y = 2 \times 157 $
$ 2x + 5y = 2 $
Since we have $ 2(3) + 5(-1) = 1$, we can see
$ 2(2 \times 3) + 5(2 \times -1) = 2 $
So a solution is $x = 6, y=-2$
(iii) -1570 is $-10 \times \gcd(314, 785)$.
Since we have $ 2(3) + 5(-1) = 1$, we can see
$ 2(-10 \times 3) + 5(-10 \times -1) = -10 $
So a solution is $x = 30, y=10$
Determine the least positive integer values of the following linear combinations ($x$ and $y$ are integers):
(a) $132x + 174y$
(b) $102x + 207y$
(c) $99x + 1008y$
(d) $666x + 3020y$
The least positive integer values of $ax + by$ is $\gcd(a,b)$.
(a) 6
(b) 3
(c) 9
(d) 2