12.12. Prove that if $a$ dan $b$ are integers, not both zero, then there are infinitely many pairs of integers $m,n$ such that $(a,b)=am+bn$.
12.13. Prove that if $c$ is a positive integer, then $(ac,bc)=(a,b)\cdot c$.
12.15. Prove that if $p$ is a prime and $a$ is an integer, and $a$ is not divisible by p, then $(a,p)=1$.
12.22. Prove that if $a,b,c$ are integers, not all zero, then they have a greatest common divisors, which can be written as a linear combination of $a,b,$ and $c$.
13.16. Prove that if $n$ is an integer, then $\sqrt{n}$ is rational iff $n$ is a perfect square.
13.19. Prove that if $a$ and $b$ are positive integers, then
$$(a,b)[a,b]=ab$$
when [a,b] is least common multiple.
Solat Idul Fitri di ‘s-Hertogenbosch
8 months ago
Solution
ReplyDelete12.12.
We will estabilish the existence of solution first.
Let $a$ and $b$ be any nonzero integers. Consider the set $S$ of all positive integers of the form $am+bn$, where $m$ and $n$ are integers. This set is nonempty and so by well-ordering principle there is a least number, $d=ax+by$. By the division algorithm, there are also integers $q$ and $r$ such that $a=qd+r$ with $0 \leq r < d$. But $r=a-qd=a-q(ax+by)=a(1-qx)+b(-qy)$. It follows that $r=0$ or otherwise $r \in S$, contradicting the fact that $d$ is the least elemen $\in S$. Hence $a=qd$, that is, $d|a$. Similarly, we will have $d|b$. So that $d$ is the common divisor of $a$ and $b$.
In other side, if $c$ is common divisor of $a$ and $b$ then $c|ax+by=d$, then we should have $d$ is the gratest common divisor of $a$ and $b$.
That is, there are solution of the system equation $ax+by=(a,b)$.
Now, the infinitely solution. If$(x_0,y_0)$ is solution then
$$(x+\dfrac{kb}{(a,b)},y-\dfrac{ka}{(a,b)})$$
with $k$ is any integer, is also solution the the equation.
The second come from following :
ReplyDeleteby 12.12
$(ac,bc)=acx+bcy$ for some integer $x,y$. And also :
$(a,b)|a$ then $(a,b)c|acx$,
$(a,b)|b$ then $(a,b)c|bcy$,
Then
$(a,b)c| acx +bcy=(ac,bc)$
So, $(a,b)c|(ac,bc)$.
Conversely,
$(a,b)c=[am+bn]c=ac(m)+bc(n)$ will follow that
$(ac,bc)|(a,b)c$
(by corollary xx.xx)
Then because we have
$(a,b)c|(ac,bc)$ and
$(ac,bc)|(a,b)c$
then $(a,b)c=(ac,bc)$.