The mathematician wrote a three-digit whole number on the whiteboard and asked the students to decide whether that is a prime number or not. Big-brain Billy divided it from 2 to 31 but didn’t find any factors. There he stopped and stated that the given number is a prime.
a) Was he right? Why?
b) Is 2021 a prime number?
How will I even begin with this question!
If a positive integer $n$ is composite then $n=ab$ where $a$ and $b$ are positive integers with $a>1$ and $b>1.$ It cannot be true that $n=ab$ with $a>\sqrt n$ and $b>\sqrt n,$ otherwise we would have $n=ab>a\sqrt n>(\sqrt n)(\sqrt n)=n$. So if $n$ is composite then $n$ has a factor ($a$ or $b$) that is greater than $1$ but less than or equal to $\sqrt n. $
We have $32^2=2^{10}=1024>999.$ So if $100\le n\le 999$ then $\sqrt n <32.$
Big-brain Billy could do better. If $a$ is a factor of $n$ with $1<a\le \sqrt n$ then $a$ has a prime factor $p$ with $p\le a\le \sqrt n,$ so $p$ is a $prime$ factor of $n$ with $p\le \sqrt n.$ So if $100\le n\le 999$ and $n$ is not divisible by any of $2,3,5,7,11,13,17,19,23,29,31$ then $n$ is prime.
There are some short-cuts for finding whether $n$ is divisible by $a.$ The notation $a|n$ means $a$ divides $n.$ In base ten:
$3|n$ iff $3$ divides the sum of the digits of $n$ (...iff $3$ divides the sum of the digits of the sum of the digits of $n,$ etc.).$
$5|n$ iff the last digit of $n$ is $0$ or $5.$
$11|n$ iff $11$ divides the alternating $\pm$-digit sum of $n.$ E.g. $11$ does not divide $+2-0+2-1=3$ so $11$ does not divide $2021$.
If $k$ is an integer then $a|n$ iff $a|(n- ka).$ Choose $k$ so that the last digit of $ka$ is the last digit of $n$.
E.g. $29|2021$ iff $29|(2021+29)=2050$ iff $29|205$. Also $29|205$ iff $29|(2)(205)=410$ iff $29|41.$ Therefore $29$ does not divide $2021$ .
Similarly $31|2021$ iff $31|(2021-31)=1990$ iff $31|199$ iff $31|(199+31)=230$ iff $31|23$. Therefore $31$ does not divide $2021.$
