Divisibility

• Given a and b, any integer can be written in the form $a=$$qb +$$r$, where q,b,a and r are integers, and r is the remainder when a is divided by b.
• If m is a factor of n, m divides n. This can be represented as $m\mid n$
• A linear combination of a and b is a number in the form $xa +$$yb$, where x and y are integers
• $k\mid a$ and $k\mid b$ means that $k\mid {(xa+yb)}$
• Euclid’s lemma states that if p is prime and $p|ab$, then $p|a$ or $p|b$.
• If $n>1$ and $n|(a-b)$, then $a \equiv b (mod n)$.
• The set of integers modulo n can be represented by $\mathbb{Z}_n$.
• If $a \equiv A(mod n)$ and $b\equiv B(modn)$, then:

  • $a +$$b \equiv A+$$B(modn)$
  • $a - b \equiv A-B(modn)$
  • $ab\equiv AB(modn)$
• A unit in modulo n is a number that has an inverse in mod n, such that $a\times a^{-1} \equiv 1 (modn)$. An inverse can only be found if a and n are coprime.
• If a is a unit modulo n, the order of a mod n is the smallest integer k such that $a^k\equiv 1(modn)$.
• A linear congruence is in the form $ax+$$b\equiv cx+$$d(modn)$.
• When $ax\equiv b(modn)$, if a and n are coprime, we can multiply by the inverse of a to find the value of $x(modn)$.
• For $ax\equiv b(modn)$, if a and n are not coprime, either:

  • $hcf(a,n)\nmid b$, which means there are no solutions.
  • $hcf(a,n)\mid b$, which means that there are multiple solutions. We can divide all values in the equation by $hcf(a,n)$, and solve the resulting relation. We can then add the new value of n to the first solution to find all others.
• The following are some common divisibility tests:

  • 2 - check that the units digit is even.
  • 3 - check that the sum of all digits is divisible by 3.
  • 4 - check that the last 2 digits are divisible by 4.
  • 5 - check that the last digit is a 0 or a 5.
  • 8 - check that the last 3 digits are divisible by 8.
  • 9 - check that the sum of the digits is divisible by 9.
  • 11 - check that the alternating sum of the digits is divisible by 11.
• To design a divisibility test for a number n such that $hcf(n,10) =$$1$:

  1. Start with 10a+b.
  2. Find the inverse of 10 in n.
  3. If possible, choose the negative inverse of 10 in n.
  4. Multiply the expression by the inverse.
• When testing x for divisibility by n using the expressions $10a+$$b$ and $a+$$mb$:

  1. Set $10a+$$b=$$x$.
  2. Find the integers a and b.
  3. Put a and b into the expression $a+$$mb$.
  4. Set $a+$$mb =$$x$.
  5. Repeat until the result is clearly either divisible by n or not divisible by n.
• In number base n, only digits up to n can be used. If n is greater than 10, we can use letters to represent further digits (A,B,C…).
• In number base n, each digit in base n is multiplied by an increasing power of n, starting with 0 for the units digit, and then added together to convert to base 10.
• To convert to base n, divide the number by n, and the remainder is the first digit in the representation in base n. Repeat the process with the integer part of the result until it becomes 0.