Practice Problems Week 10

• You may collaborate with up your peers.

Problems

1. Perform the following conversions:
   1. 27 in base 10 to base 2
   2. 1111111 in base 2 to base 10
   3. 101 in base 10 to base 2
2. Compute GCD(1240, 6660)
3. Let a be a positive integer. Prove that GCD(a, a+1) = 1
4. Prove that GCD(a, a+2) = 1 if a is odd, and GCD(a, a+2) = 2 if a is even
5. Show that if $a \equiv b (\text{mod n})$ and if $b \equiv c (\text{mod n})$, then $a \equiv c (\text{mod n})$
6. Simplify the following congruences:
   1. $15x \equiv 9 \text{ (mod 25)}$
   2. $6x \equiv 3 \text{ (mod 9)}$
   3. $14x \equiv 42 \text{ (mod 50)}$
7. Describe the general solution for x and y, if it exists: $35x + 47y = 1$

References:

Problems 1-3 were drawn from:

• chapter 6 of Precalculus, 3rd corrected edition by S&Z
• Chapter 2 and 4 of Number Theory, in context and interactive
• Chapter 5.2 of Discrete Mathematics, an open introduction, 3rd edition