Online Course Discussion Forum

MC III Number Theory 1.14

 
 
Picture of Alan Ding
MC III Number Theory 1.14
by Alan Ding - Thursday, 14 March 2024, 8:26 PM
 

I don't know how to do 1.14. Help! Didn't follow in class either. All help is greatly appreciated.


If a, b, c, d are positive integers and ad-bc=1, show that the fraction (a+b)/(c+d) is irreducible.

 
Picture of John Lensmire
Re: MC III Number Theory 1.14
by John Lensmire - Friday, 15 March 2024, 9:41 AM
 

Let me give the idea and a quick hint here. (Note: The course recording has the answer to the question I'll ask in the hint below.)

This problem is related to Bezout's Theorem:

  • If gcd(a,b) = 1, then there exist m and n so that a*m + b*n = gcd(a,b).

In fact, it's exploring the converse that is relevant here:

  • If there exist m and n so that a*m + b*n = k, then k is a multiple of gcd(a, b).
  • Or really the special case of: if there exist m and n so that a*m + b*n = 1, then gcd(a,b) = 1.

Start first by making sure these make sense.

Now back to the problem: To show (a+b)/(c+d) is irreducible, we need to show gcd(a+b, c+d) = 1. This means we want to look for m and n so that (a+b)*m + (c+d)*n = 1. Hint: Nothing above has used the fact that ad-bc=1, so that is probably relevant here!

Hope this help!