Online Course Discussion Forum

Help on II-A Number Theory

Picture of Kevin Song
Help on II-A Number Theory
by Kevin Song - Saturday, March 13, 2021, 2:08 PM

Hello, I don't know how to do 3.21 and 3.26

Thanks, Kevin

Picture of John Lensmire
Re: Help on II-A Number Theory
by John Lensmire - Monday, March 15, 2021, 12:01 PM

Some hints:

For 3.21: Remember given the prime factorizations of two numbers a and b, the GCD has a prime factorization that is the minimum value of all the exponents in the prime factorizations (where we include 0 as a possible exponent if the prime appears in one factorization but not the other). How would this be method be modified if we have a third number? Another hint: note that min(a,b,c) is the same as min ( min(a,b), c).

For 3.26: Remember that by Bezout's identity there are integers k and l such that 3k + 11l = gcd(3,11) = 1. (It is also easy to find k and l that work). This should help with part a). (The values of 500 three dollar bills and 100 eleven dollar bills do not affect the problem.) Since change is given, the fact that k and l might need to be negative doesn't matter for part a), but it does matter for part b) where change is not given. As a hint, it possible to pay for something that costs 19 dollars?