Divisibility

**shadow_2145** · July 7th 2008, 02:01 PM

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.

**o_O** · July 7th 2008, 02:13 PM

#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$

**Jhevon** · July 7th 2008, 02:51 PM

Originally Posted by shadow_2145

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

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$

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$

**o_O** · July 7th 2008, 02:55 PM

#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

**shadow_2145** · July 7th 2008, 03:05 PM

Woo, thanks. I was having problems incorporating the definitions

**Jhevon** · July 7th 2008, 03:06 PM

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!

**Jhevon** · July 7th 2008, 03:08 PM

Originally Posted by shadow_2145

Woo, thanks. I was having problems incorporating the definitions

ok, so i take it you are familiar with the definitions i gave then? did you see how o_O and i applied them?

**shadow_2145** · July 7th 2008, 07:16 PM

Yes, I am okay for now.

Thank you.

Thread: Divisibility

LinkBack

Thread Tools

Display

Divisibility

Similar Math Help Forum Discussions

Divisibility 11

Divisibility (gcd) 10

Divisibility (gcd) 9

Divisibility (gcd) 8

Divisibility

Search Tags