- #1
j9mom
- 31
- 0
Homework Statement
if (a,c)=1 and (b,c)=1 prove that (ab,c)=1
Homework Equations
I know that (a,c)=1 says that au+cv=1 and bs+ct=1 prove abq+cr=1
The Attempt at a Solution
I set au+cv=bs+ct now I don't know what to do
aPhilosopher said:do you know the theorem that if d|ab, then d|a or d|b?
Dick said:That's false. 6|(3*4) but 6 doesn't divide 3 or 4. You had better say the word 'prime' at some point.
j9mom said:Wait... x is a prime number greater than 1 that divides c
j9mom said:Wait... x is a prime number greater than 1 that divides c
j9mom said:Let x = a prime number greater than 1 that divides c. Assume (ab,c)=x. Based on the theorem we know that x|a or x|b. However, based on the given that (a,c)=1 and (b,c)=1, we know that x does not divide a and x does not divide b. Hence there is a contradiction and x cannot be a prime number greater than 1. Since we know there is no prime number less than 1, x must equal 1
Dick said:You can't assume BOTH x|c AND (ab,c)=x without justifying it.
aPhilosopher said:Yes you can. By definition. What can't be assumed is that (ab, c)=x and that x is prime.
A greatest common divisor, also known as a greatest common factor, is the largest positive number that divides two or more numbers without leaving a remainder.
The easiest method to find the greatest common divisor is to list all the factors of each number and then identify the largest number that appears in each list. Another method is to use the Euclidean algorithm, which involves dividing the larger number by the smaller number and repeating the process until the remainder is 0.
The greatest common divisor is used in many mathematical concepts, such as simplifying fractions, finding equivalent fractions, and solving equations involving fractions. It is also used in computer science, particularly in finding the smallest common multiple and reducing fractions in programming.
No, the greatest common divisor must always be smaller than or equal to the smaller number. This is because any number that divides both numbers must also divide the smaller number, making it the largest possible common factor.
The greatest common divisor is the largest number that divides two or more numbers without leaving a remainder, while the least common multiple is the smallest number that is a multiple of two or more numbers. The two concepts are related, as the greatest common divisor can be used to find the least common multiple.