Proving the Divisibility of Relatively Prime Integers

[STEMucator]

Homework Statement

I've got two questions out of my textbook. I'll list both of them and my attempts below.

(1) Suppose : $a, b, c\in Z, a|c \space \wedge \space b|c.\space$If a and b are relatively prime, show ab|c. Show by example that if a and b are not relatively prime then ab does not divide c ( Didn't know how to do does not divide in latex ).

(2) Show that 5n+3 and 7n+4 are relatively prime for all n ( I'm assuming the book means $\forall n\in N$).

Homework Equations

Supposing that p is a prime, then p has a unique prime factorization :

$p = p_{1}^{α_1} ... p_{n}^{α_n}$

Also I believe that (1) is Euclid's Lemma backwards...

I think that gcd(a,b) = as + bt for some integers s and t will be useful for (2) not positive yet though.

The Attempt at a Solution

(1) We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations. Let :

$a = a_{1}^{α_1} ... a_{n}^{α_n}$

$b = b_{1}^{β_1} ... b_{n}^{β_n}$

be prime factorizations for a and b.

If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt.

Am I going in the right direction here? I'll save (2) for after (1) is figured out.

 

[jbunniii]

So far so good. Think about the prime factorization of $c$. By the way, to be properly general, you shouldn't use $n$ for the number of distinct prime factors of both $a$ and $b$.

 

[STEMucator]

So far so good. Think about the prime factorization of $c$. By the way, to be properly general, you shouldn't use $n$ for the number of distinct prime factors of both $a$ and $b$.

Heya jbun, duly noted about n, I'll try not to be so sloppy.

Anyway, I digress.

c is not necessarily prime though? Why would I require its factorization.

 

[jbunniii]

c is not necessarily prime though? Why would I require its factorization.

Because you want to show that ab divides c, and you have prime factorizations for a and b.

By the way, I'm not sure I understand your question. A prime number has a trivial prime factorization, consisting of itself. Prime factorizations are more interesting for numbers that are NOT prime.

 

[STEMucator]

Because you want to show that ab divides c, and you have prime factorizations for a and b.

By the way, I'm not sure I understand your question. A prime number has a trivial prime factorization, consisting of itself. Prime factorizations are more interesting for numbers that are NOT prime.

Ahh I had a derp for a moment there. My bad.

So let's see if I can continue this now. So I should take either one of the cases a|c or b|c and prove that if either a or b is relatively prime, then ab|c ( Because of symmetry of course )?

 

[jbunniii]

So let's see if I can continue this now. So I should take either one of the cases a|c or b|c and prove that if either a or b is relatively prime, then ab|c ( Because of symmetry of course )?

"If either a or b is relatively prime" doesn't make any sense. An individual number can't be relatively prime. PAIRS of numbers can be relatively prime. If a and b are relatively prime, that means their prime factorizations don't have any prime factors in common. So think about what that implies about the prime factorization of c.

 

[STEMucator]

"If either a or b is relatively prime" doesn't make any sense. An individual number can't be relatively prime. PAIRS of numbers can be relatively prime. If a and b are relatively prime, that means their prime factorizations don't have any prime factors in common. So think about what that implies about the prime factorization of c.

So then I would have ( excuse the n for now ) :

$a|c \Rightarrow a_{1}^{α_1} ... a_{n}^{α_n}|c$

and obviously

$b|c \Rightarrow b_{1}^{β_1} ... b_{n}^{β_n}|c$

Excuse my noobish thought process here, but I'm not quite sure what these tell me about the prime factorization of c? Would these imply that some a_i^α_i and some b_j^β_j divide c?

 

[jbunniii]

Excuse my noobish thought process here, but I'm not quite sure what these tell me about the prime factorization of c? Would these imply that some a_i^α_i and some b_j^β_j divide c?

In fact, it's easy to see that they all divide c.

Hopefully have encountered the following elementary theorem: if $m$ divides $n$ and $n$ divides $p$, then $m$ divides $p$. This is true for any integers, not just prime numbers.

So take one of the factors of $a$: $a_i^{\alpha_i}$ divides $a$, and $a$ divides $c$, therefore by the elementary theorem above, $a_i^{\alpha_i}$ divides $c$. Same argument holds for the factors of $b$.

So far, we haven't used the fact that the $a_i$'s and $b_i$'s are prime. You will need to take advantage of that in order to finish the theorem.

 

[STEMucator]

In fact, it's easy to see that they all divide c.

Hopefully have encountered the following elementary theorem: if $m$ divides $n$ and $n$ divides $p$, then $m$ divides $p$. This is true for any integers, not just prime numbers.

So take one of the factors of $a$: $a_i^{\alpha_i}$ divides $a$, and $a$ divides $c$, therefore by the elementary theorem above, $a_i^{\alpha_i}$ divides $c$. Same argument holds for the factors of $b$.

So far, we haven't used the fact that the $a_i$'s and $b_i$'s are prime. You will need to take advantage of that in order to finish the theorem.

Surprisingly this theorem is not directly in my textbook, but I know that it is true ( I've seen the proof before ). I'll take a moment to put everything together nicely in one post here...

We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations. Let :

$a = a_{1}^{α_1} ... a_{t}^{α_t}$

$b = b_{1}^{β_1} ... b_{s}^{β_s}$

be prime factorizations for a and b. So we know that some $a_{i}^{α_i}, 1≤i≤t$ divides a. Since $a_{i}^{α_i}|a$ and $a|c$, we know $a_{i}^{α_i}|c.$

Similarily, we know that some $b_{i}^{β_i}, 1≤i≤s$ divides b. Since $b_{i}^{β_i}|b$ and $b|c$, we know $b_{i}^{β_i}|c.$

If a|c, we know that there is some integer q such that c = aq and if b|c, we know that there is some integer p such that c = bp.

Hmm as per your comment about the ai's and bi's. Since they are prime... hmm I'm trying to formulate the point you're trying to get across. Does it have something to do with the gcd of them? ( This is my first time writing a proof like this one so sorry if I seem a bit lost ).

 

[jbunniii]

Surprisingly this theorem is not directly in my textbook, but I know that it is true ( I've seen the proof before ). I'll take a moment to put everything together nicely in one post here...

We have by hypothesis that a and b are relatively prime integers That is, they are composed of unique prime factorizations.

Well, all integers have unique prime factorizations. You don't need the fact that a and b are relatively prime in order for that to be true. So "that is" is the wrong wording here.

$a = a_{1}^{α_1} ... a_{t}^{α_t}$

$b = b_{1}^{β_1} ... b_{s}^{β_s}$

be prime factorizations for a and b. So we know that some $a_{i}^{α_i}, 1≤i≤t$ divides a. Since $a_{i}^{α_i}|a$ and $a|c$, we know $a_{i}^{α_i}|c.$

Actually, this is true for all of the $a_{i}^{\alpha_i}$, not just some.

Similarily, we know that some $b_{i}^{β_i}, 1≤i≤s$ divides b. Since $b_{i}^{β_i}|b$ and $b|c$, we know $b_{i}^{β_i}|c.$

Same comment here.

Hmm as per your comment about the ai's and bi's. Since they are prime... hmm I'm trying to formulate the point you're trying to get across. Does it have something to do with the gcd of them? ( This is my first time writing a proof like this one so sorry if I seem a bit lost ).

Well, you need the fact that if p and q are distinct prime numbers, and p and q both divide c, then pq divides c. Then you build up from there.

However, this is a pretty grungy proof. There is a much slicker one involving the fact that you mentioned in your original post. As you said, if a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1.

Now, big hint: try multiplying both sides of that equation by c, and see what you can conclude.

 

[STEMucator]

Well, all integers have unique prime factorizations. You don't need the fact that a and b are relatively prime in order for that to be true. So "that is" is the wrong wording here.Actually, this is true for all of the $a_{i}^{\alpha_i}$, not just some.Same comment here.Well, you need the fact that if p and q are distinct prime numbers, and p and q both divide c, then pq divides c. Then you build up from there.

However, this is a pretty grungy proof. There is a much slicker one involving the fact that you mentioned in your original post. As you said, if a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1.

Now, big hint: try multiplying both sides of that equation by c, and see what you can conclude.

I did notice something about the gcd indeed... Tossing out everything else and using this slick trick :

"If a and b are relatively prime, that means their gcd is 1, which in turn means that we can find integers x and y such that ax + by = 1"

Would I need what I said earlier? :

"If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt."

So : gcd(a,b) = 1 = ax + by ( For some integers x and y ).

ax + by = 1
c(ax+by) = c

... What can I conclude? c|c, but that's obvious.

 

[jbunniii]

"If a|c, we know that there is some integer s such that c = as and if b|c, we know that there is some integer t such that c = bt."

So : gcd(a,b) = 1 = ax + by ( For some integers x and y ).

ax + by = 1
c(ax+by) = c

... What can I conclude? c|c, but that's obvious.

Well, you just said that c = as and c = bt. Try making those substitutions in c(ax+by) = c.

 

[STEMucator]

Wait wait waaaaait something just hit me. Let me re-write this nice and clean.

If a and b are relatively prime, we know that gcd(a,b) = 1 = ax + by for some integers x and y.

If a|c, we know that there is some integer q such that c = aq. If b|c, we know that there is some integer t such that c = bt.

Now, since a|c, then a|bt. Since b|c, then b|aq.

Now consider :

ax + by = 1
acx + bcy = c

Since we know that a|bt, we know that a|acx. We also know that because b|aq, b|bcy as well.

Is this what you were getting at?

 

[jbunniii]

Wait wait waaaaait something just hit me. Let me re-write this nice and clean.

If a and b are relatively prime, we know that gcd(a,b) = 1 = ax + by for some integers x and y.

If a|c, we know that there is some integer q such that c = aq. If b|c, we know that there is some integer t such that c = bt.

Now, since a|c, then a|bt. Since b|c, then b|aq.

Now consider :

ax + by = 1
acx + bcy = c

Since we know that a|bt, we know that a|acx. We also know that because b|aq, b|bcy as well.

Is this what you were getting at?

Not exactly. I'm not sure why you needed any manipulation to conclude that a|acx and b|bcy. This is obvious because acx = a(cx) and bcy = b(cy).

You have established that this is true:

acx + bcy = c

The goal is to conclude that ab|c. You can do this by showing that ab|acx and ab|bcy, because then ab divides both terms on the left hand side. This means that ab divides the left hand side. Therefore it also divides the right hand side.

So, all you need to do is show that ab|acx, and ab|bcy.

 

[STEMucator]

Not exactly. I'm not sure why you needed any manipulation to conclude that a|acx and b|bcy. This is obvious because acx = a(cx) and bcy = b(cy).

You have established that this is true:

acx + bcy = c

The goal is to conclude that ab|c. You can do this by showing that ab|acx and ab|bcy, because then ab divides both terms on the left hand side. This means that ab divides the left hand side. Therefore it also divides the right hand side.

So, all you need to do is show that ab|acx, and ab|bcy.

EDIT : I'll attempt this in the morning... my brain has been off for hours now and I'm basically struggling to see obvious things. I'll post when I'm fresh.

 

[STEMucator]

Okay! So after some rest and a little bit of time looking at this I think I've got it.

Since a|c and b|c, there exist integers x and y such that ax = by = c. Also, since gcd(a,b)=1, we know there exist integers s and t such that 1 = as + bt.

Now consider :

1 = as + bt
c = asc + btc
c = as(by) + bt(ax)
c = (ab)sy + (ab)tx
c = ab(sy + tx)

Hence we see that ab|c as desired.

As for an example, take a = 4, b = 6 and c = 36. So gcd(a,b) = 2 which means a and b are not relatively prime.

Notice that 4|36 and 6|36, however ab=24$\nmid$36 as desired.

 

[jbunniii]

Okay! So after some rest and a little bit of time looking at this I think I've got it.

Since a|c and b|c, there exist integers x and y such that ax = by = c. Also, since gcd(a,b)=1, we know there exist integers s and t such that 1 = as + bt.

Now consider :

1 = as + bt
c = asc + btc
c = as(by) + bt(ax)
c = (ab)sy + (ab)tx
c = ab(sy + tx)

Hence we see that ab|c as desired.

As for an example, take a = 4, b = 6 and c = 36. So gcd(a,b) = 2 which means a and b are not relatively prime.

Notice that 4|36 and 6|36, however ab=24$\nmid$36 as desired.

Perfect!

 

[STEMucator]

Perfect!

Phew! Sleep does wonders for me haha.

I'll attempt the second question after my class, but I am pretty sure I know how to do it. I'll post my attempt later.

 

[STEMucator]

Okay now for #2 : Show that 5n+3 and 7n+4 are relatively prime for all integers n.

This is equivalent to showing that gcd(5n+3, 7n+4) = 1 for all integers n. We know that the gcd is a linear combination of a and b, so it suffices to show that there exists a linear combination of 5n+3 and 7n+4 that gives 1.

So, let : gcd(5n+3, 7n+4) = d = s(5n+3) + t(7n+4) for some integers s and t.

Clearly by some very easy inspection, take s = 7 and t = -5. Then we observe that :

7(5n+3) - 5(7n+4) = 35n + 21 - 35n - 20 = 1 = d.

Since d|5n+3 and d|7n+4 we know d|1 ( Clearly the only positive divisor of 1 is 1 ). Therefore we conclude that d = 1 = gcd(5n+3,7n+4).

Is this good?

 

[jbunniii]

Okay now for #2 : Show that 5n+3 and 7n+4 are relatively prime for all integers n.

This is equivalent to showing that gcd(5n+3, 7n+4) = 1 for all integers n. We know that the gcd is a linear combination of a and b, so it suffices to show that there exists a linear combination of 5n+3 and 7n+4 that gives 1.

So, let : gcd(5n+3, 7n+4) = d = s(5n+3) + t(7n+4) for some integers s and t.

Clearly by some very easy inspection, take s = 7 and t = -5. Then we observe that :

7(5n+3) - 5(7n+4) = 35n + 21 - 35n - 20 = 1 = d.

Since d|5n+3 and d|7n+4 we know d|1 ( Clearly the only positive divisor of 1 is 1 ). Therefore we conclude that d = 1 = gcd(5n+3,7n+4).

Is this good?

Yes, that works! Suppose your very easy inspection hadn't worked - do you know another way to solve the problem?

 

[STEMucator]

Yes, that works! Suppose your very easy inspection hadn't worked - do you know another way to solve the problem?

Hmm... perhaps strong induction? I'm not really sure how I would've come to a conclusion here otherwise.

 

[jbunniii]

Hmm... perhaps strong induction? I'm not really sure how I would've come to a conclusion here otherwise.

Do you know the Euclidean algorithm for calculating the gcd?

 

[STEMucator]

Do you know the Euclidean algorithm for calculating the gcd?

Hmm I believe that I would continue subtracting the larger number from the smaller one over and over again until both numbers are the same, then that number I get at the end is the gcd of both my original numbers. I see now that if I had done that with 5n+3 and 7n+4 with 7n+4 being the bigger number first I would see that their gcd = 1.

 

[jbunniii]

Hmm I believe that I would continue subtracting the larger number from the smaller one over and over again until both numbers are the same, then that number I get at the end is the gcd of both my original numbers. I see now that if I had done that with 5n+3 and 7n+4 with 7n+4 being the bigger number first I would see that their gcd = 1.

Sounds right, you can always use this method if you can't find the gcd some other slicker way.

 

[STEMucator]

Sounds right, you can always use this method if you can't find the gcd some other slicker way.

Thanks for pointing that out, I had completely forgotten about it. I'm wondering if you could have a quick look at something else for me? I'm pretty sure I know what I'm doing, but having your approval is re-assuring.

This : https://www.physicsforums.com/showthread.php?t=639142