# Divisibility

• Jul 7th 2008, 03:01 PM
Divisibility
1) If $(a,b) = d$, prove that $(\frac{a}{d}, \frac{b}{d}) = 1$

Not quite sure how to do that one..

2) If $a|(b+c)$ and $(b,c)=1$, prove that $(a,b) = 1 = (a,c)$

Suppose $d|a$ and $d|b$

$a=du$ for some u in Z
$b=dv$ for some v in Z

$a|(b+c)$
$b+c=aw$
$c=aw-b$
$c=duw-dv$
$c=d(uw-v)$
$d|c$

Now, how do I say that (a,b) = 1 = (a,c) ?

Thanks for any help.
• Jul 7th 2008, 03:13 PM
o_O
#1
Let $x = \left(\frac{a}{d}, \frac{b}{d}\right) \: {\color{blue} \geq 1}$ (gcd of any two integers is always greater than or equal to 1).

By definition, there are some integers $r, s$ such that $xr = \frac{a}{d} \: \: \iff \: \: dxr = a$ and $xs = \frac{b}{d} \: \: \iff \: \: dxs = b$.

In other words, dx is a common divisor of $a$ and $b$. Since (a,b) = d, then $dx \leq d \: \: \Rightarrow \: \: x \leq 1$.

However, recall that $x \geq 1$. So, $x = \left(\frac{a}{d}, \frac{b}{d}\right) = 1$
• Jul 7th 2008, 03:51 PM
Jhevon
Quote:

1) If $(a,b) = d$, prove that $(\frac{a}{d}, \frac{b}{d}) = 1$

i really like o_O's solution to this. but here is how i was thinking of proving it. being very unimaginative, i like to go by definitions a lot and leave the fancy stuff to geniuses like o_O (Rofl)

disclaimer (?): to avoid having to say, "for some integers..." or "where so and so are integers..." all the time (which you should do!) just assume that whenever i introduce a new variable it is an integer.

recall the properties of the gcd:

Definition: $(a,b) = d$ means that:
(1) $d \mid a$ and $d \mid b$
(2) If there is $x$ such that $x \mid a$ and $x \mid b$, then $x \mid d$

also: $(a,b) = d \implies na + mb = d$....this is pretty much equivalent to condition (1), we will use this a lot.

these are the properties we will use in answering both questions. i hope you are familiar with them. now lets get to it.

Proof:

Assume $(a,b) = d$. then $na + mb = d$. dividing both sides by $d$ (note $d \ne 0$) we get $n \bigg( \frac ad \bigg) + m \bigg( \frac bd \bigg) = 1$, so that 1 satisfies condition (1) above. now, to show it satisfies condition (2), assume there is some $x$ such that $x \Bigg| \frac ad$ and $x \Bigg| \frac bd$. then $\frac ad = kx$ and $\frac bd = lx$. plug these into the equation that satisfies condition (1), we find that $(nk)x + (ml)x = (nk + ml)x = 1 \implies x \mid 1$. so that 1 satisfies condition (2), and we have $\bigg( \frac ad, \frac bd \bigg) = 1$ $~ \blacksquare$

Quote:

2) If $a|(b+c)$ and $(b,c)=1$, prove that $(a,b) = 1 = (a,c)$

Suppose $d|a$ and $d|b$

$a=du$ for some u in Z
$b=dv$ for some v in Z

$a|(b+c)$
$b+c=aw$
$c=aw-b$
$c=duw-dv$
$c=d(uw-v)$
$d|c$

Now, how do I say that (a,b) = 1 = (a,c) ?

Thanks for any help.
we will use the same plan of attack on this guy. we need to verify the two conditions for 1 in regards to both $(a,b)$ and $(a,c)$.

Proof:

Assume $a \mid (b + c)$ and $(b,c) = 1$. then we have:

$b + c = ak$...................(eq 1)
$nb + mc = 1$................(eq 2)

From (eq 1), $b = ak - c$ ..............(eq 3), and $c = ak - b$ .................(eq 4).

plugging in (eq 3) into (eq 2) and simplifying, we get: $(nk)a + (m - n)c = 1$, so that 1 satisfies condition (1) in regards to (a,c)

plugging in (eq 4) into (eq 2) and simplifying, we get: $(mk)a + (n - m)b = 1$, so that 1 satisfies condition (1) in regards to (a,b)

now, proving condition (2) for both of these is pretty much identical to the way i did it in the last question. i leave it to you. $\blacksquare$
• Jul 7th 2008, 03:55 PM
o_O
#2
Let $d_{1} = (a,b) \geq 1$ which implies $d_{1} | b$ Through your reasoning, we see that $d_{1} | c$. ( $d_{1}$ is a common divisor of b and c)

Similarly, if we let $d_{2} = (a, c) \geq 1$ (implying $d_{2} | c$), we see that $d_{2} | b$. ( $d_{2}$ is also a common divisor of b and c)

However, $(b,c) = 1 \: \: \Rightarrow d_{1} = d_{2} = 1$.

Edit: Ah beaten by Jhevon ;)
• Jul 7th 2008, 04:05 PM
Woo, thanks. I was having problems incorporating the definitions :(
• Jul 7th 2008, 04:06 PM
Jhevon
Quote:

Originally Posted by o_O
#2
Let $d_{1} = (a,b) \geq 1$ which implies $d_{1} | b$ Through your reasoning, we see that $d_{1} | c$. ( $d_{1}$ is a common divisor of b and c)

Similarly, if we let $d_{2} = (a, c) \geq 1$ (implying $d_{2} | c$), we see that $d_{2} | b$. ( $d_{2}$ is also a common divisor of b and c)

However, $(b,c) = 1 \: \: \Rightarrow d_{1} = d_{2} = 1$.

Edit: Ah beaten by Jhevon ;)

did you change something? i notice you deleted the your last post. it seems as if it was identical to this one. anyway, i thanked you in your last post. it stays even after you delete it, so no worries. nice solutions! (Yes)
• Jul 7th 2008, 04:08 PM
Jhevon
Quote: