- #1

STEMucator

Homework Helper

- 2,075

- 140

## Homework Statement

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

(1) Suppose : [itex]a, b, c\in Z, a|c \space \wedge \space b|c.\space[/itex]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 [itex]\forall n\in N[/itex]).

## Homework Equations

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

[itex]p = p_{1}^{α_1} ... p_{n}^{α_n}[/itex]

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 :

[itex]a = a_{1}^{α_1} ... a_{n}^{α_n}[/itex]

[itex]b = b_{1}^{β_1} ... b_{n}^{β_n}[/itex]

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.