- #1
- 2,076
- 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.