I'm going to be a TA in an introductory course in mathematics at a technical university this fall, focusing on mathematics that the students should already be familiar with but that might need refreshing before the courses in linear algebra and calculus start.

One of the things in the course is basic factorization - both for integers and polynomials. I don't think anyone will have trouble finding the first few primes such as $2$, $3$ and $5$, but it got me thinking as to whether there is a systematic approach when trying to factor slightly higher primes such as $17$ or $31$.

Generally if I happen to be doing integer factorization I try to "feel" which prime might be possible to factor out, but that is not a very helpful thing to tell students.

Is there a better method to quickly find the factors? Obviously excluding calculators, computers and the such.

edit: Quick example exercise

Perform integer factorization on $2108$. It is obvious that $2108 = 2 * 2 * 527$.

However is there a method for quickly finding the two remaining factors, $17$ and $31$? Just by looking at $527$, I would say it is not apparent to most people which prime numbers (or even what range beyond the double digits) to start trying.

  • $\begingroup$ For finding primes: Sieve of Eratosthenes See wikipedia: en.wikipedia.org/wiki/Sieve_of_Eratosthenes $\endgroup$ – William Jul 29 '14 at 12:28
  • $\begingroup$ Also computationally, all known algorithms for factorization are fairly slow in a technical sense. Practically, if you know all the primes below the square root of a number, you can avoid some computation. $\endgroup$ – William Jul 29 '14 at 12:34
  • $\begingroup$ Have you read the Wikipedia page on integer factorization? $\endgroup$ – Bill Dubuque Jul 29 '14 at 13:00
  • $\begingroup$ "...when trying to factor slightly higher primes such as 17 or 31." Factoring primes is trivial. What you meant was, finding slightly higher prime factors. If you're going to teach, I beg you to say to your students exactly what you mean, and not something sorta kinda like what you mean. They will find the mathematics hard enough, without having to decipher sloppy statements of problems, definitions, solutions, and so on. $\endgroup$ – Gerry Myerson Jul 29 '14 at 13:14
  • $\begingroup$ Thank you for helping me improve. I will not be teaching in English, nor is English my first language. $\endgroup$ – abberg Jul 29 '14 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.