# 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.

- Java's