1. ## Divisibility

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

Not quite sure how to do that one..

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

Suppose $\displaystyle d|a$ and $\displaystyle d|b$

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

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

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

Thanks for any help.

2. #1
Let $\displaystyle 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 $\displaystyle r, s$ such that $\displaystyle xr = \frac{a}{d} \: \: \iff \: \: dxr = a$ and $\displaystyle xs = \frac{b}{d} \: \: \iff \: \: dxs = b$.

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

However, recall that $\displaystyle x \geq 1$. So, $\displaystyle x = \left(\frac{a}{d}, \frac{b}{d}\right) = 1$

1) If $\displaystyle (a,b) = d$, prove that $\displaystyle (\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

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: $\displaystyle (a,b) = d$ means that:
(1) $\displaystyle d \mid a$ and $\displaystyle d \mid b$
(2) If there is $\displaystyle x$ such that $\displaystyle x \mid a$ and $\displaystyle x \mid b$, then $\displaystyle x \mid d$

also: $\displaystyle (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 $\displaystyle (a,b) = d$. then $\displaystyle na + mb = d$. dividing both sides by $\displaystyle d$ (note $\displaystyle d \ne 0$) we get $\displaystyle 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 $\displaystyle x$ such that $\displaystyle x \Bigg| \frac ad$ and $\displaystyle x \Bigg| \frac bd$. then $\displaystyle \frac ad = kx$ and $\displaystyle \frac bd = lx$. plug these into the equation that satisfies condition (1), we find that $\displaystyle (nk)x + (ml)x = (nk + ml)x = 1 \implies x \mid 1$. so that 1 satisfies condition (2), and we have $\displaystyle \bigg( \frac ad, \frac bd \bigg) = 1$ $\displaystyle ~ \blacksquare$

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

Suppose $\displaystyle d|a$ and $\displaystyle d|b$

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

$\displaystyle a|(b+c)$
$\displaystyle b+c=aw$
$\displaystyle c=aw-b$
$\displaystyle c=duw-dv$
$\displaystyle c=d(uw-v)$
$\displaystyle 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 $\displaystyle (a,b)$ and $\displaystyle (a,c)$.

Proof:

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

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

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

plugging in (eq 3) into (eq 2) and simplifying, we get: $\displaystyle (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: $\displaystyle (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. $\displaystyle \blacksquare$

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

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

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

Edit: Ah beaten by Jhevon

5. Woo, thanks. I was having problems incorporating the definitions

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

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

However, $\displaystyle (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!