Divisibility Duel

A number theorist goes on a quest of determining if a number is prime. That may sound like a simple task (after all, it either is a prime, or it isn't), but it turns out to be a very very difficult question to answer. For example:

\[ \text{ Is } 1234567891011121314151617 \text{ prime?} \]

In this case, since the digit sum is 81, we can apply the divisibility rule of 9 and conclude that 9 divides 1234567891011121314151617. Thus it is not a prime number! We have slain the dragon, with our knowledge of the divisibility rules.

Tips to help you get started:

1. The number 1 is not a prime!
2. The only even prime number is 2.
3. Understanding why the rules work makes it easy for you to remember them.
4. Develop your own rules for larger numbers!
5. To check divisibility by a composite number, factor it first!

Back to Quiz: Divisibility Duel

Being able to find the factors and multiples of a number helps us in:

• Prime Factorization: By quickly testing small primes, we can hopefully factor a large number down into smaller terms. Remember that we only need to test until \( \sqrt{n} \)! (Do you know why?)
• Greatest Common Divisor and Lowest Common Multiple: Finding the GCD and LCM of several numbers is easily done if we know their prime factorization, and taking the minimum and maximum, respectively, of their exponents. (Do you know why?)