Assignment 5 (pdf)

Make sure to write complete proofs. Try to avoid skipping steps. Write clear sentences.

1. True or False: If the remainder of doing Euclidean Division of a by c is r, i.e. if \(a=qc + r\) with certain conditions on r, and the remainder of doing Euclidean Division of b by c is s, then the remainder of doing Euclidean Division of \(a+b\) by c is \(r+s\). Prove or provide counter-example.
2. True or False: If \(\gcd(a,b) = 1\) and \(\gcd(a,c) = 1\), then \(\gcd(a, bc) = 1\). Prove or provide counter-example.
3. Using the Euclidean algorithm, find concrete numbers \(x\) and \(y\) such that \(245x + 356y = 1\).
4. True or False: For given \(a, b\), if we can solve \(ax+by = c\), then we can also solve \(ax+by = d\) for any \(d\geq c\). Prove or provide counter-example.
5. True or False: The equation \(2x+by=c\) has a solution for all \(c\) if and only if \(b\) is an odd number. Prove or provide counter-example.