Divisibility

For integers a\ne 0 and b, we will say that “a divides b” and write a\mid b if there is an integer c such that b=ac.
- Also “ $a$ is a factor of $b$ ” or “ $b$ is a multiple of $a$ ”.
- For example, $3\mid 9$ but $3\nmid 10$ .
We will use the concept of divisibility often, but for now, just a few key theorems.
For integers a, b, and c,…
- Theorem: $a\mid b$ iff $b/a$ is an integer.
- Theorem: If $a\mid b$ then $a\mid bc$ for all $c$ .
- Theorem: If $a\mid b$ and $a\mid c$ , then $a\mid (b+c)$ .
  
  Proof: If $a\mid b$ and $a\mid c$ , then there are integers $d$ and $e$ such that $b=ad$ and $c=ae$ .
  
  Then, $b+c=ad+ae=a(d+e)$ . Thus, $a\mid (b+c)$ .∎
- Theorem: If $a\mid b$ and $b\mid c$ , then $a\mid c$ .
  
  Proof: If $a\mid b$ and $b\mid c$ , then there are integers $d$ and $e$ such that $b=ad$ and $c=be$ .
  
  Then, $c=be=a(bd)$ . Thus, $a\mid c$ .∎
- Corollary: If $a\mid b$ and $a\mid c$ , then $a\mid mb+nc$ for all integers $m$ and $n$ .
  
  Proof: From the above, we know that $a\mid mb$ and $a\mid nc$ . Then, $a\mid mb+nc$ .∎
Theorem: For an integer a and positive integer d, there are unique integers q and r with 0\le r \lt d such that a=dq+r.
- This theorem is called The Division Algorithm. It's not an algorithm, but that's still what it's called.
- If you refer to $q$ as the quotient and $r$ as the remainder, the theorem makes a lot of sense.
- If you divide $a$ by $d$ , you get quotient $q$ and remainder $r$ . The theorem says the exist and are unique.
- When we need these values, we will write $a\mathop{\mathbf{div}}b = q$ and $a\mathop{\mathbf{mod}}b = r$ .
For example,
- $23\mathop{\mathbf{div}}5 = 4$ and $23\mathop{\mathbf{mod}}5 = 3$ and $23=5\cdot 4 + 3$ .
- $100\mathop{\mathbf{div}}7 = 14$ and $100\mathop{\mathbf{mod}}7 = 2$ and $100=7\cdot 14 + 2$ .
- $35\mathop{\mathbf{div}}5 = 7$ and $35\mathop{\mathbf{mod}}5 = 0$ and $35=7\cdot 5 + 0$ .
Most programming languages have operators to get these values. On integers in C: b/a and b%a.
Theorem: For integers $a$ and $b$ with $b\gt 0$ , we have $a\mid b$ iff $b\mathop{\mathbf{mod}}a = 0$ .

Proof: First, if $a\mid b$ , then there is a n integer $c$ such that $b=ac$ . In the division algorithm, $c$ is the quotient with a remainder of $0$ . Thus, $b\mathop{\mathbf{mod}}a = 0$ .

Now if $b\mathop{\mathbf{mod}}a = 0$ then we have $b=aq+0$ in the division algorithm, so we see that $a\mid b$ .∎
You have probably used that fact in a program to test divisibility.
```
if ( n%2 == 0 ) { /* n is even */
  …
}
```

Modular Arithmetic

For integers $a$ and $b$ , and a positive integer $m$ , we will say that “ $a$ is congruent to $b$ modulo $m$ ” and write $a\equiv b\ (\text{mod } m)$ if $m$ divides $a-b$ .
Theorem: For integers $a,b,m$ with $m>0$ , $a\equiv b\ (\text{mod } m)$ iff $a\mathop{\mathbf{mod}}m=b\mathop{\mathbf{mod}}m$ .

Proof: First suppose that $a\mathop{\mathbf{mod}}m=b\mathop{\mathbf{mod}}m=r$ . Then from the definition, there are integers $p$ and $q$ such that $a=pm+r$ and $b =qm+r$ . Now, $a-b=pm-qm=m(p-q)$ . Thus, we see that $m\mid (a-b)$ , so $a\equiv b\ (\text{mod } m)$ .

Now suppose that $a\equiv b\ (\text{mod } m)$ . [Left as a homework exercise. …] Thus $a\mathop{\mathbf{mod}}m=b\mathop{\mathbf{mod}}m$ .∎
In other words, $a\equiv b\ (\text{mod } m)$ if they have the same remainder when divided by $m$ .

Pseudorandom Numbers

[An application of the divisibility stuff.]
It is common to need random numbers in programs.
- In games to generate random behaviour in non-player characters.
- Statistical simulation/sampling.
- In cryptography to generate a key that it is impossible for an attacker to know (without just guessing every possible value).
Problem: your computer is entirely deterministic. There's no way to get randomness out of it.
- Unless your computer has a hardware random number generator: a few processors and chipsets do.
- The OS can get a few “true” random values by taking keystroke timing, mouse movements, network I/O, etc. That's unguessable if done right, but limited: can't generate very many values because it doesn't have enough to work with.
If you need random values in a program, you need something else.
A pseudorandom number generator is an algorithm that generates values that are not random, but appear to be random enough.
- “Random enough”: are hard to predict, uniform (each value as likely as any other to be generated), seem to be random, etc.
- A pseudorandom number is definitely good enough for games, for example.
- Probably good enough for statistical sampling: as long as it's uniform it should do.
- Maybe not good enough for cryptography: “hard to predict” isn't the same as “impossible to predict”.
One way to produce random numbers: a linear congruential generator. We choose four integers:
- A modulus $m$ .
- A multiplier $a$ with $2\le a \lt m$ .
- A increment $c$ with $0\le c \lt m$ .
- A seed $x_0$ with $0\le x_0 \lt m$ .
The linear congruential generator will generate a sequence of pseudorandom values x_n with x_n = (ax_{n-1} + c)\mathop{\mathbf{mod}}m\,.
- From the definition of $\mathbf{mod}$ , these values are clearly integers from $0$ to $m-1$ .
Let's try it with $m=100$ , $a=41$ , $c=19$ , and $x_0=33$ : $\begin{align*} x_0 &= 33 \\ x_1 = (41x_{0} + 19)\mathop{\mathbf{mod}}100 &= 72 \\ x_2 = (41x_{1} + 19)\mathop{\mathbf{mod}}100 &= 71 \\ x_3 = (41x_{2} + 19)\mathop{\mathbf{mod}}100 &= 30 \\ x_4 = (41x_{3} + 19)\mathop{\mathbf{mod}}100 &= 49 \\ x_5 = (41x_{4} + 19)\mathop{\mathbf{mod}}100 &= 28 \\ &\vdots \\ x_{98} = (41x_{97} + 19)\mathop{\mathbf{mod}}100 &= 35 \\ x_{99} = (41x_{98} + 19)\mathop{\mathbf{mod}}100 &= 54 \\ x_{100} = (41x_{99} + 19)\mathop{\mathbf{mod}}100 &= 33 \\ x_{101} = (41x_{100} + 19)\mathop{\mathbf{mod}}100 &= 72 \end{align*}$
Observations:
- Since $x_n$ only depends on $x_{n-1}$ , once we hit $x_0$ again, we'll enter a loop and generate the same values again.
- The best period of the loop we can hope for is $m$ : we can only generate $m$ distinct values before getting back to $x_0$ .
- We should choose a large $m$ .
- If we had chosen $c=20$ above, we would have only generated 5 values before looping.
- Choices of the constants matter a lot: choosing them badly makes the generator useless.
This sequence is obviously predictable.
- If I tell you I just generated 71, you can tell me the next value.
- If you know the seed, you can predict all of the values.
- If you know I generated my private cryptographic key, and the next number generated was 35, you can figure out my private key without too much work.
- It would have been much harder to predict if I only showed you the first digit of each $x_i$ : 7, 7, 3, 4, 2,… , 3, 5.
If we have a little bit of “true” randomness, we can at least use that to generate the seed.
- … and most pseudorandom number implementations do.
Linear congruential generators are a realistic pseudorandom number technique.
- Java's java.util.Random uses one with $m=2^{48}$ .
- Most C implementations use one with $m=2^{31}$ or $2^{32}$ .
- In each case, they don't return all of the bits (just like the “first digit” example above).
- But it's not the only algorithm: Python, Ruby, R use the Mersenne twister algorithm.