Online Course Discussion Forum
Help on II-A Number Theory
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?