1. Prove the following:

    Theorem (Some properties of divisibility)

    Let \(a,b,c \in \mathbb{Z}\) and \(a \neq 0\). Then:
    i. if \(a \mid b\) and \(a \mid c\), then \(a \mid (b+c)\);
    ii. if \(a \mid b\), then \(a \mid kb\) for any integer \(k\);
    iii. if \(a \mid b\) and \(b \mid c\), then \(a \mid c\).

  2. List all the divisors, proper divisors, and prime divisors of 28.
  3. Let \(n,d\in\mathbb{Z}^+\), how many integers less than \(n\) are divisible by \(d\)?
  4. If someone claims that given integers \(a,b,c\in \mathbb{Z}^+\), if \(a\mid bc\), then either \(a\mid b\) or \(a\mid c\). What do you say?
  5. Provide a definition of a composite number using the concept of proper divisors.

  6. Here is a definition:

    Definition 1 (trivial divisors)

    Given an integer \(n\), we say that 1,-1,\(n\), and \(-n\) are the trivial divisors of \(n\).

    Define prime and composite numbers using the concept of trivial divisors.

  7. Prove that for any integer \(n\), if \(n\) is even, then \(n^2\) is even. Use the definitions of even numbers and divisibility in your proof.
  8. Prove that the product of an even integer with an odd integer is even.
  9. Prove that for any composite integer \(n\), \(n = ab\) for some \(a,b \in \mathbb{Z}\) where \(1 < a < n\) and \(1 < b < n\).
  10. Prove that if \(a\) and \(b\) are integers with \(a\mid b\), then \(a\) is odd or \(b\) is even.
  11. Prove that if \(a\) and \(b\) are nonzero integers, \(a\mid b\) and \(a+b\) is odd, then \(a\) is odd.
  12. Prove that if \(a\) is an integer that is not divisible by 3, then \((a +1)(a +2)\) is divisible by 3.
  13. Prove that if \(a\) is a positive integer, then 4 does not divide \(a^2 +2\).

  14. Define digit_count(n, base=10) that returns the number of digits of n in base base.

    Criteria and notes
    • Everything needs to stay as number, no conversion to string or any other sequence.
    • You can use math modules log(n, base), but be careful about rounding errors; the workaround is to call log with a very small amount added to n, say 1e-12; and don’t forget to convert what you get from log to int.

  15. Define bconvert(n, fr=10, to=2) that converts a given number from base fr to base to.

    Criteria and notes
    • Assume the base will always be less than or equal to 10.
    • First generate string or sequence output, this is simpler to find.
    • Do not look at solutions on the web until you burn your fuses.
    • Once the string/sequence solution is at hand, solve the problem by returning a number that mimics the result. For instance this version must return the decimal number 101 to the call bconvert(5,10,2).

  16. Define a function isprime(n).

    Criteria and notes
    • Apply the naive iterative method of checking divisors from 2 upto to n.
    • To increase efficiency, consider the following facts:
      • If \(n\) is composite, \(n= ab\) with \(1< a < \sqrt{n}\) or \(1< b < \sqrt{n}\)
      • All primes greater than 3 can be written in the form \(6k \pm 1\) for some integer \(k\).
    Solutions

    With while:

     def isprime(n):
     """Return True if n is prime."""

     if n <= 1 or n % 2 == 0 or n%3 == 0:
         return False

     divides = lambda a,b: b % a == 0
     divisor = 5
     while divisor * divisor <= n:
         if divides(divisor,n) or divides(divisor+2,n):
             return False
         divisor += 6
     return True

    With proc:

     def isprime(n):
     """Return True if n is prime."""

     if n <= 1 or n % 2 == 0 or n%3 == 0:
         return False

     divides = lambda a,b: b % a == 0

     return proc((True, 5),
                  lambda s: s[1]*s[1] <= n and s[0],
                  lambda s: ((not
                               (divides(s[1],n)
                                or divides(s[1]+2,n)),
                                s[1]+6)))[0]