# Why teach factorization of integers?

Why is factorization of integers important in a first number theory course at an undergraduate level? Where is factorization used in real life? Are there examples which have a real impact? I am looking for examples which will motivate students.

-
Many commonly used cryptography algorithms (e.g., the ones you use to shop online while keeping your credit card number secure) depend on the fact that there is no efficient algorithm for factoring large numbers. Factorization is one of the classical problems of mathematics; it's discussed in Euclid. –  Ben Crowell May 29 '14 at 14:04
Welcome to the site! Could you describe the context a bit more. At what level are the students? Is this about secondary education and a first encounter with number theory or about a first course in number theory at the university level. –  quid May 29 '14 at 14:23
I find that it makes quite a bit of mental arithmetic much easier. –  Chris C May 29 '14 at 14:35
A first course in number theory at undergraduate level. –  matqkks May 29 '14 at 14:38
@matqkks: Is there a particular textbook you're using (or intending to use)? –  J W May 29 '14 at 15:11

Luckily there's a book

The Joy of Factoring. Samuel S. Wagstaff, Jr.

that answers this exact question -- see the review on the linked page. In addition to cryptography, the book motivates an interest in factoring via repunits, repeating decimal fractions, perfect numbers, Gauss's interest in factoring and the Cunningham project.

-
I think readers might easily be misled by the statement that the book "answers this exact question." To clarify, the book very briefly discusses said topics in 10 pages of the first chapter, titled "Why Factor Integers". But this is not the primary topic of the book. Further, rather than ancient recreational applications, most number theorists or algebraists would list much deeper reasons for studying factorization. –  Bill Dubuque May 30 '14 at 1:29
@BillDubuque: I took the phrase "this exact question" from the review. I don't have the book in front of me and haven't looked at it for quite a while, but in addition to the "recreational" motivation in the first chapter, I seem to remember the fourth chapter (How factors are used) and the seventh chapter (Elliptic curves) provide further reasons for why one might study factoring (in the context of number theory). –  ncr May 30 '14 at 3:00

There is (at least) one significant reason behind the factorization: the relevant intuition. For example

• it allows you to think of natural numbers as vectors (e.g. $\gcd$ and $\mathrm{lcm}$ become component-wise $\min$ and $\max$);
• it allows you to think of the Chinese remainder theorem as base-reencoding from prime-based number system.

There are also other good reasons, like the problem's importance in cryptography or as basic example of unique factorization domain or principal ideal domain. Still, the intuitions and mental tools factorization provides seem enough of a reason by itself.

I hope this helps $\ddot\smile$

-

As far as "real life" goes, it's fairly boring, but I honestly think the best use is simply number sense.

It's not complete prime factorization that's important, IMO it's not super important to your average undergrad that $288 = 3^2 \cdot 2^5$, but the general process of $288 = 2 \cdot 144 = 2 \cdot 12 \cdot 12$ will make it much easier to multiply 3-4 digit numbers in your head. Or the inverse, simply that "oh, 288 is about 12 times bigger than 24". While that specific number may not be useful, the general method is.

Of course, depending on your subfield of mathematics that's not necessarily an overwhelmingly useful skill, but it's useful for one-the-fly calculations in "real life". As much as we like to make fun of them, "if Sally has 12 apples..." problems do come up occasionally in planning meetings and the like, and the ability to get a quick intuitive breakdown of numbers can speed things up.

-

Where is factorization used in real life?

It is used when we simplify fractions. For example, to simplify $\frac{15}{51}$ to $\frac{5}{17}$ one must know that $15=3\times 5$ and $51=3\times 17$.

It is used when we need to know how many objects having a common value are needed to get a given value. For example, to find out how many $16$-US-fluid-ounce cups of a softdrink are needed to fill up a $1$-US-gallon container, you need to know that $1$ US gallon = $128$ US fluid ounces = $8\times 16$ US fluid ounces.

-

Comparison of number systems: Why is the decimal system mathematically worse than the duodecimal system? Why is the sexigesimal system so useful, that it's still used even if nearly everything else (outside of the US, Liberia and Burma) is decimal?

The answer is the factoring of these numbers.

-
I wouldn't say that decimal system is worse than the duodecimal, in fact the popularity of the former is an argument that it's perhaps the other way around. –  dtldarek May 29 '14 at 16:22
@dtldarek Ah, I forgot to add mathematically. –  Toscho May 30 '14 at 9:36

I hope this is different enough from dtldarek's answer. It's too long for a comment:

The uniqueness of factorization over the integers is an important theoretical tool Gauss used it (Art. 16, Disquisitiones Arithmeticae) to establish many basic facts. Properties of the GCD and LCM can be proved quite easily by students. Gauss also uses it to prove propositions about congruences, the Euler phi function, etc. As for the phi function, one can say in general that multiplicative functions cannot be understood without understanding factorization. The notion of relatively prime is based on factorization. I suppose that goes more generally for multiplicative number theory.

I'm sometimes uncertain whether "real life" includes what people actually do. There are quite a few number theorists, software engineers, researchers at private and government institutions, and so on, who use number theory, not to mention many other mathematical fields that rely on number theory. If factorization is important for understanding number theory, then it is important for these things, too.

-

Factoring into primes is a very fundamental operation in number theory. It pops up all over the place.

-
While to the point in my opinion, this answer is so terse that I suspect it is not very helpful for somebody actually asking the question, and it could be helpful if you would include some examples. (The votes are not mine.) –  quid May 30 '14 at 19:19