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