Keo's Notes

Divisibility

8 min read

Number-Theory links: Primes

Basic Divisibility Properties

Let

  1. (reflexive property)
  2. (transitivity property)
  9. has an even number of divisors s.t

Euclid’s Division Lemma

GCD

Properties

  1. is prime or
  2. If , ,
  3. , , ,
  4. If is a common divisor of
  6. , ,
    2. By definition and
    3. So has to be a common divisor of and . And , by definition, is the greatest number that satisfies that. Therefore
    2. By property 7,

Euclid’s Division Algorithm

By repeatedly apply property 8: . You can find the of any 2 numbers easily

Bézout’s Identity

s.t You can figure out and by going through the Euclidean Algorithm backwards and collecting like terms. Two integers , are coprime if so by Bezout’s Identity s.t Proof

  1. Consider the set of .
  2. Since consists of non-negative integers there exists a minimal element . So
  3. By the division algorithm ,
  4. This means that is a linear combination of . If then but this contradicts the minimality of so .
  5. Hence . The same argument can be made to show that meaning .
  6. Since and , so we get and so

This also proves that as was the minimal element.

LCM

  1. ,
  2. If is common multiple of and and ,
  3. is a common multiple of and
  4. ,
  6. ,

Number of Divisors

Properties

  1. Given the
  2. there are distinct ordered pairs such that
  3. ,
  4. ,
  6. is Multiplicative.

Explanations

  1. Given the
    1. This is because any divisor must be in the form with . So for each there are choices for . Since they are independent you multiply.
  2. there are distinct ordered pairs such that
    1. *This is because are divisors of so they must have the form and since there are options for each :

So you multiply number of choices together. 3. , 1. 1. You can split the divisors into pairs so their product is multiplying all together you get Then multiply by yielding 2. 1. You can split the divisors into pairs so their product is multiplying all together you get 4. , 1. Let be the divisors of . The rest of the divisors are . In each set there are numbers so (or if is a perfect square) Since are distinct positive integers there can be at most so 5. 1. Using we can deduce that therefore is square. 6. is Multiplicative. 1. Let and with meaning the share no prime factors. 2. and 3. since they share no prime factors so there is no crossover in primes and this is the proper prime factorisation. (If a, b weren’t coprime they would share factors and this would not be the proper prime factorisation: you could get terms. This means that is not completely multiplicative) 4.

Sum of Divisors

Definition

is defined as the sum of divisors of . This can be written as

Properties

  2. is Multiplicative

Explanations

    1. Let then the divisors will have the form . Every possible divisor appears exactly once so each combination of will appear exactly once which can be written as which are geometric series, therefore
  1. is Multiplicative
    1. Let
    2. Every positive divisor .
    3. Therefore, the sum of all positive divisors of is given by .
    4. This multiple summation can be factored into a product of separate geometric series:
    5. Now suppose and are two positive integers with , and let and where the and are distinct primes (since and are coprime).
    6. Then , and using the previous identity for , we get:

Graph View

Backlinks