Math115a (Youtube)

  1. Lecture 03/04: Divisibility and Euclid's Algorithm
  2. Lecture 05: Primes
  3. Lecture 06: Multiplicative Functions
  4. Lecture 07: Binomial Coefficients
  5. Lecture 08: Applications of Binomial Coefficients
  6. Lecture 09: Congruences
  7. Lecture 10: Applications of Fermat's Theorem
  8. Lecture 11: Euler's Theorem
  9. Lecture 12: Wilson's Theorem
  10. Lecture 13: Chinese Remainder Theorem
  11. Lecture 14: Euler Totient Function
  12. Lecture 15: Numerical Calculations
  13. Lecture 16: More Numerical Calculations
  14. Lecture 17: Factorization
  15. Lecture 18: Cryptography
  16. Lecture 19: Hansel and Newton's Method
  17. Lecture 20: p-adic Numbers
  18. Lecture 21: Congruences Modulo a Prime

Math115a (Attempted Problems)

    1.2: Divisibility

  1. 1.2: Problem 00: Show that \([a,b] = \frac{ab}{(a,b)}\) for any integers \(a,b\).
  2. 1.2: Problem 19: Any set of integers that relatively prime in pairs are relatively prime.
  3. 1.2: Problem 21: Prove that if an integer of the form \(6k + 5\), then it is necessarily of the form \(3k-1\), but not conversely.
  4. 1.2: Problem 24: Prove that if \(n\) is composite, it must have a prime factor \(p \leq \sqrt{n}\).
  5. 1.2: Problem 26: Let \(s\) and \(g > 0\) be given integers. Prove that integers \(x\) and \(y\) exist satisfying \(x + y = s\) and \((x, y) = g\) if and only if \(g \mid s\).

    6. 1.4: Primes

  6. 1.3: Problem 06: Show that every positive integer \(n\) has a unique expression of the form \(n = 2^rm\), \(r \geq 0\), \(m\) a positive odd integer.
  7. 1.3: Problem 14: Evaluate \(ab, p^4\) and \(a+b, p^4\) given that \((a,p^2) = p\) and \((b, p^3) = p^2\) where \(p\) is prime.
  8. 1.3: Problem 16: Find a positive integer \(n\) such that \(n/2\) is a square, \(n/3\) is a cube, and \(n/5\) is a fifth power.
  9. 1.3: Problem 18: Prove that \((a^2,b^2) = c^2\) if \((a,b) = c\).
  10. 1.3: Problem 19: Let \(a\) and \(b\) be positive integers such that \((a,b) = 1\) and \(ab\) is a perfect square. Prove that \(a\) and \(b\) are perfect squares. Prove that the result generalizes to \(k\)th powers.
  11. 1.3: Problem 20: Given \((a,b,c)[a,b,c] = abc\), prove that \((a,b) = (b,c) = (a,c) = 1\).

    12. 1.4: The Binomial Theorem

  12. 1.4: Problem 04: Suppose that \(S\) contains \(2n\) elements and that \(S\) is partitioned into \(n\) disjoint subsets each one containing exactly two elements of \(S\). Show that this can be done in precisely

    13. 2.1: Congruences

  13. 2.1: Problem 02: Exhibit a complete residue system module 17 composed entirely of multiples of 3.
  14. 2.1: Problem 06: Prove that if \(p\) is a prime and \(a^2 \equiv b^2 (\bmod p)\), then \(p \mid (a + b)\) or \(p \mid (a - b)\)
  15. 2.1: Problem 08: Prove that any number that is a square must have one of the following for its units digit: \(0,1,4,5,6,9\)
  16. 2.1: Problem 12: Prove that 19 is not a divisor of \(4n^2 + 4\) for any integer \(n\).
  17. 2.1: Problem 17: Show that \(61! + 1 \equiv 63! + 1 \equiv 0 \pmod{71}\).
  18. 2.1: Problem 18: Show that if \(p \equiv 3 \pmod{4}\), then \(\left(\frac{p-1}{2}\right)! \equiv \pm 1 \pmod{p}\)
  19. 2.1: Problem 19: Prove that \(n^6 - 1\) is divisible by \(7\) if \((n,7) = 1\).
  20. 2.1: Problem 20: Prove that \(n^7 - n\) is divisible by \(42\) for any integer \(n\).
  21. 2.1: Problem 21: Prove that \(n^{12} - 1\) is divisible by \(7\) if \((n,7) = 1\).
  22. 2.1: Problem 23: Prove that \(n^{13} - n\) is divisible by \(2,3,5,7\) and \(13\) for any integer \(n\).
  23. 2.1: Problem 24: Prove that \(n^{12} - a^{12}\) is divisible by \(13\) if \(n\) and \(a\) are prime to \(13\).
  24. 2.1: Problem 27: Prove that \(\frac{1}{5}n^{5} + \frac{1}{3}n^{3} + \frac{7}{15}n\) is an integer for every integer \(n\).

    25. 2.3: Chinese Remainder Theorem

  25. 2.3: Problem 02: Find all integers that satisfy simultaneously \(x \equiv 2 \pmod{3}\),\(x \equiv 3 \pmod{5}\) and \(x \equiv 5 \pmod{2}\).
  26. 2.3: Problem 07: Determine whether the congruences \(5x \equiv 1 \pmod{6}\),\(4x \equiv 13 \pmod{15}\) have a common solution, and find them if they exist.
  27. 2.3: Problem 10: Find the number of positive integers \(\leq 3600\) that are prime to \(3600\).
  28. 2.3: Problem 12: Find the number of positive integers \(\leq 7200\) that are prime to \(3600\).
  29. 2.3: Problem 14: Solve the congruences:...
  30. 2.3: Problem 16: Solve the congruence \(x^3 - 9x^2 + 23x - 15 \equiv 0 \pmod{503}\) by observing that \(503\) is a prime and that the polynomial factors into \((x-1)(x-3)(x-5)\).
  31. 2.3: Problem 17: Solve the congruence \(x^3 - 9x^2 + 23x - 15 \equiv 0 \pmod{143}\).

    32. 2.4: Techniques of Numerical Calculation

  32. 2.4: Problem 2: Show that \(2^{45} \equiv 57 \pmod{91}\). Deduce that \(91\) is composite.
  33. 2.4: Problem 14: Use Pollard rho method to locate proper divisors of the following numbers: (a) \(8,131\)

Other Notes

  1. Multiplicative Order
  2. Reptend Prime
  3. Euler Totient's Function
  4. Chinese Remainder Theorem