Turn on thread page Beta
    • Thread Starter
    Offline

    9
    ReputationRep:
    i am getting thoroughly frustrated by some basic maths i cant seem to do. Can someone please please please help just answer this question:

    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!
    Offline

    2
    ReputationRep:
    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.
    Offline

    15
    ReputationRep:
    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.
    • Thread Starter
    Offline

    9
    ReputationRep:
    so can it definitely not be done by linear combination?
    Offline

    2
    ReputationRep:
    I'm sure you must be able to do it using LCs...
    Offline

    15
    ReputationRep:
    What do you mean by linear combination?
    Offline

    15
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    9
    ReputationRep:
    (a,b) can be written in the form ax + by

    i have no idea how to prove that that is valid but it is!
    • Thread Starter
    Offline

    9
    ReputationRep:
    (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?
    Offline

    15
    ReputationRep:
    (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.
 
 
 
Turn on thread page Beta
Updated: January 11, 2005

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
    Postgraduate Open Day Postgraduate
    Wed, 30 Jan '19
  • Solent University
    Careers in maritime Undergraduate
    Sat, 2 Feb '19
Poll
Brexit: Given the chance now, would you vote leave or remain?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Equations

Best calculators for A level Maths

Tips on which model to get

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.