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.