You are Here: Home >< Maths

# Frustration at simple question watch

if (a,b) means "The highest common factor of a and b" then prove the following:

(a,b) = (a,d) = 1 implies that (a,bd) = 1

i.e. prove that if a and b are co-prime and a and d are co-prime then a and bd are co-prime.

i would ideally like to see this done using linear combinations if possible!
2. I've had a go doing it using linear combinations and not getting very far, but can't you just use the arguement that
(a,b)=1 => a and b do not share any prime factors
likewise (a,d)=1 => a and d do not share any prime factors
Therefore, if you multiply b and d, then they still won't share any primes with a. => gcd = 1.
3. Okay... I think this is a proof. By the fundamental theorem of arithmetic we can decompose a, b and d into products of primes.

a shares no common prime factors with b or d (from the question), and given that the prime factorisation is unique bd is simply the product of the prime factorisations of b and d, and hence it also shares no common prime factors with a, hence the (a, bd) = 1.
4. so can it definitely not be done by linear combination?
5. I'm sure you must be able to do it using LCs...
6. What do you mean by linear combination?
7. (Original post by Willa)
so can it definitely not be done by linear combination?
If this is what you mean by linear combinations you can say:

As a and b are coprime there exist u,v such that

ua + vb=1

As a and d are coprime there exist w,x such that

wa+xd=1.

Hence

1 = (ua+vb)(wa+xd) = (uwa+vbw+xdu)a+(vx)bd

and so a and bd are coprime.
8. (a,b) can be written in the form ax + by

i have no idea how to prove that that is valid but it is!
9. (Original post by RichE)
If this is what you mean by linear combinations you can say:

As a and b are coprime there exist u,v such that

ua + vb=1

As a and d are coprime there exist w,x such that

wa+xd=1.

Hence

1 = (ua+vb)(wa+xd) = (uwa+vbw+xdu)a+(vx)bd

and so a and bd are coprime.

that last stage doesn't convince me because arent you making the assumption that only coprime numbers can have a linear combination = 1?
10. (Original post by Willa)
that last stage doesn't convince me because arent you making the assumption that only coprime numbers can have a linear combination = 1?
It's not much of an assumption.

Say ua+vb=1 and c is a common factor of a and b, then it's also a common factor of any linear combination of a and b, and so also of 1. i.e. c=1 or -1.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: January 11, 2005
Today on TSR

### Four simple steps to get an A*

Here's all you have to do

### University open days

• University of East Anglia
All Departments Open 13:00-17:00. Find out more about our diverse range of subject areas and career progression in the Arts & Humanities, Social Sciences, Medicine & Health Sciences, and the Sciences. Postgraduate
Wed, 30 Jan '19
• Aston University
Wed, 30 Jan '19
• Solent University
Sat, 2 Feb '19
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams