Determining whether a number is prime (or “The Benefits of Square-Rooting a Number, Part I”)

Something that comes up now and again in various contexts during lessons is how to tell whether a number is prime. My usual advice has been to use divisibility rules*, and if none work, then it’s likely that the tested number is prime. Likely is not the same thing as certain, however, and, as the numbers get bigger, the divisibility rules will tend to be less and less helpful. For example, it’s easy to rule out that 51 is a composite number, i.e. not prime (and not ‘1’), but what about 1591? None of the common divisibility rules work, but that doesn’t mean 1591 is necessarily prime.

Ponte di Rialto over the Canal Grande, Venice, Italy. Completed in 1591. Photo of bridge by Saffron Blaze,

Knowing that there had to be some better way to determine whether a number is prime, I did a web search and found the following method:

To determine whether a number n is prime, square-root the number and let the result be r. Next, try to divide n by all the prime numbers that are less than r.

Let’s see how this method works with a composite and a prime number, 539 and 113 respectively.

Continue reading “Determining whether a number is prime (or “The Benefits of Square-Rooting a Number, Part I”)”

Solving tracing problems using graph theory

A couple of weeks ago, I was looking at a standardized test and came across the following “tracing” problem:

Which of the drawings below can you completely trace without lifting your pencil or retracing a previously traced part? 


When I was a teenager, I had seen similar questions to this one, but was always frustrated that I couldn’t figure out a way to solve them except by trial and error. Twenty years later, thanks to being exposed to different areas of mathematics as a tutor, I instantly saw a systematic way to answer them. Try solving the test question on your own first before reading my approach below.
Continue reading “Solving tracing problems using graph theory”