# Number Theory

## Number Theory and Prime Factorization

In trying to understand complex rhythms we are naturally led down the path of elementary number theory, as prime numbers and prime factorization come into play. A rhythm can be described as a pattern of repeated drum beats. Suppose Corey repeatedly plays a rhythm on his snare drum that is $$3$$ beats in duration and Alyssa repeatedly plays one on her bass drum that is $$4$$ beats in duration. They start playing their rhythms at the same point in time using the same tempo.  A listener would hear a repeated pattern formed from their combined rhythms as well. How many beats is the duration of this resulting pattern?

The answer actually depends on what the particular rhythms happen to be. For example, suppose that in every three beats Corey plays in the first and third beats

## C_CC_CC_CC_CC_CC_CC_CC_CC_CC_C…

and every four beats Alyssa plays on beats one and three

## A_A_A_A_A_A_A_A_A_A_A_A_A_A….

In any given beat, there are four possible combinations of sounds:

 Corey only (C), Alyssa only (A), neither Corey nor Alyssa (_), or Both Corey and Alyssa (B)

and the combination of both of them would be

## B_BCACB_BCACB_BCACB_BCAC….

which is a $$6$$ beat repeating pattern.
On the other hand if every three beats, Corey plays on beats one and two,

## CC_CC_CC_CC_CC_CC_CC_CC_CC_CC_.

and every four beats Alyssa plays on beats one, two, and three,

## AAA_AAA_AAA_AAA_AAA_AAA_AAA_

the combination of the two of them would be

## BBACBABCABB_BBACBABCABB_

which repeats every $$12$$ beats.

Despite the fact that there is a difference in the answer to the question depending on the patterns played by Corey and Alyssa, one thing that can say is that no matter what pattern Corey plays every $$3$$ beats and Alyssa plays every $$4$$ beats, the resulting pattern must repeat every $$12$$ beats since $$3\times 4 = 12$$. On the other hand, if Corey’ rhythm is $$6$$ beats long and Alyssa’ is $$4$$ beats long, then their combined pattern repeats every $$6 \times 4 = 24$$ beats, but it is also the case that we know their combined rhythms repeat in a smaller number of beats, in fact $$12,$$ because $$6$$ and $$4$$ have common a prime factor, and we know that no matter what pattern they play, their combined pattern will repeat every $$12$$ beats because $$12$$ is least common multiple of $$6$$ and $$4.$$

More generally, if Corey’ rhythm is $$m$$ beats in duration and Alyssa’ is $$n$$, their combined rhythms will repeat every $$m\times n$$ beats, but repetition will also happen in a smaller number of beats as long as $$m$$ and $$n$$ share a common prime factor. In fact, repetition will occur every $$k$$ beats, where $$k$$ is the least common multiple (or lcm) of $$m$$and $$n,$$ and this is the smallest number of beats for which we are guaranteed that repetition will occur, independent of the specific rhythms played by Corey and Alyssa.

Computing the smallest number of beats for the combined rhythm, independently of the specific rhythms in question reduces to computing the least common multiple of the numbers $$m$$ and $$n,$$ something that is done via prime factorization, that is the unique representation of a positive integer as a product of powers of prime numbers. For example, the prime factorization of $$180$$ is $$2^2\times 3^2\times 5^1.$$

The least common multiple of a pair of numbers can be easily expressed in terms of the numbers’ prime factorizations. If we write $$m$$ as a product $$p_1^{u_1}\times p_2^{u_2} \times \cdot p_r^{u_r}$$ of prime numbers raised to integer powers, and similarly write $$n$$ as a product $$p_1^{v_1}\times p_2^{v_2} \times \cdot p_r^{v_r}$$ of powers of primes, then their lcm is the product of the primes raised to the larger of the two powers

## $$lcm(m,n) = p_1^{\max\{u_1,v_1\}} p_2^{\max \{ u_1,v_1\}} \cdots p_k^{\max\{ u_k,v_k\}}.$$

For example, if $$m=15$$ and $$n=18$$ then we have $$m=2^0 \times 3^1 \times 5^1$$ and $$18 = 2^1 \times 3^2 \times 5^0,$$ and we see that

• $$2$$ is raised to the $$0$$-th power in $$m$$ and to the $$1$$-st power in $$n,$$ and the maximum of these two powers is $$1,$$
• $$3$$ is raised to the $$1$$-st power in $$m$$ and to the $$2$$-nd power in $$n,$$ and the maximum of these two powers is $$2,$$
• $$5$$ is raised to the $$1$$-st power in $$m$$ and to the $$0$$-nd power in $$n,$$ and the maximum of these two powers is $$1,$$

so the lcm of $$m$$ and $$n$$ is $$2^1 \times 3^2 \times 5^1 = 90.$$

The same problem just described arises if we want to learn how the combination of, say, triplets over quarter notes sounds rhythmically. Suppose you are programming a drum sequencer that allows for any number of beats, and you want to subdivide a measure into triplets and quarter notes so that you can hear what the combination of the two sounds like. How many beats do you need to subdivide the measure into? Again, the answer is the least common multiple of $$3$$ and $$4$$, which is $$12.$$