Question

Ludka has divided 23 by all prime numbers below 23. Because there is always a remainder, she says that 23 must be a prime number.










Ludka looks at Eric’s board on finding factors and wonders what is the best way that she can improve her method.

A board that says finding factors of 15 and 15 divided by 1 equals 15. 15 divided by 3 equals 5. 15 divided by 5 equals 3. 15 divided by 15 equals 1. The last two are labeled as repeated factor pairs. The numbers 1, 15, 3, and 5 are on the side.
Select an answer

She should be dividing by every number, not just prime numbers.
She could have stopped at 13 because it is over half of 23 so the next possible factor will be 23 itself.
She could have stopped at 5 because the answer, 4 remainder 3, was smaller than 5 so the pattern would start repeating now.
Her method is correct. She is right to check all of the prime numbers less than 23.

Answer 1

She could have stopped at 5.

Reason: if d divides n then there is a complementary factor q = n/d. Once your divisor d exceeds q (equivalently once d > sqrt(n)), any new divisor would pair with a smaller factor you’ve already checked. For 23, sqrt(23) ≈ 4.8, and 23 ÷ 5 = 4 remainder 3 (quotient 4 < 5), so you don’t need to try larger divisors.