Problem 1: Find r such that 3¹³ &equiv r (mod 11) and 0 &le r < 11.

3¹³ &equiv 3³ * 3³ * 3 ³ * 3 ³ * 3 &equiv 27 * 27 * 27 * 27 * 3 &equiv 5 * 5 * 5 * 5 * 3 &equiv 25 * 25 * 3 &equiv 3 * 3 * 3 &equiv 27 &equiv 5 (mod 11)

Problem 2: Prove or disprove: for any integers a, b, and c, if b | a and c | a then bc | a.

Counterexample: a = b = c = 5. 5 | 5 and 5 | 5 but it is not the case that 25 | 5.

Problem 3: Prove or disprove: the square root of any irrational number is irrational.

The statement is false. A counterexample is -sqrt(2), which is irrational and does not have a real square root. Since all irrational numbers are real it also does not have an irrational square root.

We can prove that the square root of any positive irrational number is irrational.

Proof: Suppose there is a positive irrational number x with a rational square root y. Since y is the square root of x we have x = y² = y * y. But then x is the product of two rational numbers and so x is rational too, which contradicts the assumption that x is irrational. Therefore there is no irrational number with a rational square root. In other words, every positive irrational number has an irrational square root.

Problem 4: Prove that for all integers n, if n³ is a multiple of 7 then n is a multiple of 7. (Hint: prove the contrapositive using the quotient-remainder theorem.)

The contrapositive is "if n is not a multiple of 7 then n³ is not a multiple of 7.

Proof: Suppose n is not a multiple of 7. Then it is not that case that n &equiv 0 (mod 7). There are six cases remaining from the quotient-remainder theorem:

• n &equiv 1 (mod 7). Then n³ &equiv 1³ &equiv 1 (mod 7);
• n &equiv 2 (mod 7). Then n³ &equiv 2³ &equiv 8 &equiv 1 (mod 7);
• n &equiv 3 (mod 7). Then n³ &equiv 3³ &equiv 27 &equiv 6 (mod 7);
• n &equiv 4 (mod 7). Then n³ &equiv 4³ &equiv 64 &equiv 1 (mod 7);
• n &equiv 5 (mod 7). Then n³ &equiv 5³ &equiv 125 &equiv 6 (mod 7); and
• n &equiv 6 (mod 7). Then n³ &equiv 6³ &equiv 216 &equiv 6 (mod 7).

Problem 5: Prove that the cube root of 7 is irrational.

Proof: Suppose that the cube root of 7 is rational. Then there are integers p and q such that p³/q³ = 7. Furthermore, we can find such a p and q with no common factors. We then have p³ = 7q³, so p³ is a multiple of 7 and by problem 4, p is a multiple of 7. Then there is an integer k such that p = 7k. By substitution we now have 7q³ = (7k)³ and q³ = 7 * 7 * k³. So q³ is a multiple of 7 and by problem 4 q is a multiple of 7. Now p and q have a common factor (7), which contradicts that p and q have no common factors. Therefore, the cube root of 7 is irrational.

Problem 6: Compute gcd(3003,1560) using the Euclidean Algorithm.

gcd(3003, 1560) = gcd(1560, 1443) since 3003 = 1 · 1560 + 1443
gcd(1560, 1443) = gcd(1443, 117) since 1560 = 1 · 1443 + 117
gcd(1443, 117) = gcd(117, 39) since 1443 = 12 · 117 + 39
gcd(117, 39) = gcd(39, 0) since 39 = 3 · 39 + 0
gcd(39, 0) = 39 bceause gcd(a, 0) for any positive integer a.
Therefore, gcd(3003, 1560) = 39.

Problem 7: Write the following using summation or product notation.

• 1 + 4 + 7 + 10 + 13
  

  4
  &Sigma	(3i + 1)
  i=0

• (n + 1) * (n + 2) * (n + 3) * ... * (2n)
  

  n
  &Pi	(n + i)
  i=1

• 10 - 17 + 26 - 37 + 50 - 65
  

  8
  &Sigma	(i2 + 1)(-1)i+1
  i=3

Problem 8: Prove that any amount more than 1 cent can be made with 3 cent stamps and at most two 2 cent stamps.

Proof: Base cases: 2 cents can be made with one 2-cent stamp, 3 cents with one 3-cent stamp, and 4 cents with two 2-cent stamps.

Induction step: Suppose k > 4 and any amount from 2 cents to k-1 cents can be made with 3-cent stamps and at most two 2-cent stamps. [We now show that k cents can be made with 3-cent stamps and at most two 2-cent stamps.] Since k > 4, k-3 is between 2 and k-1 and so by the inductive hypothesis, k-3 cents can be made with 3-cent stamps and at most two 2-cent stamps (that is, there are integers a and b such that k-3 = 3a + 2b and a >= 0 and 0 <= b <= 2). Adding a 3-cent stamp gives k cents total (so that k = 3(a + 1) + 2b where a + 1 >= 0 and 0 <= b <= 2).

Problem 9: Define a sequence by a₁ = 2, a₂ = 6, and a_n = a_n-1 + (a_n-2)² for n &ge 3. Prove that, for all positive integers n, a_n &equiv 2 (mod 4).

Proof: Base cases: a₁ = 2 and 2 &equiv 2 (mod 4), so a₁ &equiv 2 (mod 4). a₂ = 6 and 6 &equiv 2 (mod 4), so a₂ &equiv 2 (mod 4)

Induction step: Assume k > 2 and a_i &equiv 2 (mod 4) for any i such that 1 <= i < k. Since k > 2, 1 <= k-1, k-2 < k and so by the inductive hypothesis, a_n-1 &equiv 2 (mod 4) and a_n-2 &equiv 2 (mod 4). Therefore, a_n = a_n-1 + (a_n-2)² &equiv 2 + 2² &equiv 6 &equiv 2(mod 4).

Problem 10: Let P(n) be some predicate defined for integers n. Suppose that you know that P(1) is true, and that for all k &ge 1, if P(k) is true then both P(2k) and P(2k+1) are true. For what integers n may you conclude that P(n) is true?

We have P(1) -> P(2) v P(3), so P(1) gets us P(2) and P(3). We also have P(2) -> P(4) v P(5), so we have P(4) and P(5) as well. P(3) together with P(3) -> P(6) v P(7) yields P(6) and P(7)...

We can eventually get P(n) for any positive integer n.