Primes and Composites: Practice

Use the digit-sum rule for $3$ on each.

$1 + 1 + 1 = 3, \text{ so } 111 = 3 \times 37$

Thus $111$ is composite. The numbers $103$, $107$, and $109$ are all prime (each survives trial division up to $10$, since $11 \times 11 = 121$).

Screen the composites: $189$ and $195$ have digit sums divisible by $3$, and $187 = 11 \times 17$.

$191: \text{ odd, digit sum } 11, \text{ not ending in } 0 \text{ or } 5, \quad 13 \times 13 = 169 < 191 < 196 = 14 \times 14$

Test primes up to $13$: $7, 11, 13$ each leave a remainder. So $191$ is prime.

Both numbers in the pair must be prime and differ by $2$.

$71 \text{ and } 73 \to \text{both prime}, \quad 73 - 71 = 2$

So $71$ and $73$ are twin primes. In the other pairs, $85 = 5 \times 17$, $91 = 7 \times 13$, and $87 = 3 \times 29$ are composite.

Three are prime, so look for the hidden factor in the fourth.

$209 = 11 \times 19$

So $209$ is composite. (Its digit sum is $11$ and it is odd, so the rules for $2$ and $3$ miss it; you find $11$ by trial division.) The numbers $113$, $127$, and $131$ are prime.

Test the composites: $161 = 7 \times 23$, $203 = 7 \times 29$, and $217 = 7 \times 31$.

$163: \text{ odd, digit sum } 10, \text{ not ending in } 0 \text{ or } 5, \quad 12 \times 12 = 144 < 163 < 169$

Test primes up to $12$: $7, 11$ both leave a remainder. So $163$ is prime.

Factors come in pairs $d \times e = n$, and the smaller partner always satisfies $d \times d \le n$.

$d \times d > n \;\Rightarrow\; \text{no new factor pair remains to find}$

So once a trial divisor squared passes $n$, every factor would just repeat a partner already tested, and you may stop. The other statements test far too many divisors or far too few.

Three are prime, so trial-divide the fourth past the small primes.

$253 = 11 \times 23$

So $253$ is composite. Its digit sum is $10$ and it is odd, so $11$ is the first divisor that works. The numbers $151$, $157$, and $167$ are prime.

If $p > 3$ were even, then $2$ would divide it; if it were a multiple of $3$, then $3$ would divide it. Either gives a third factor.

$p \text{ prime, } p > 3 \;\Rightarrow\; p \text{ not divisible by } 2 \text{ or } 3$

So $p$ must be odd and not a multiple of $3$. It need not end in $7$ (for example $11$), and a multiple of $5$ above $5$ is composite.

Screen the others: $345$ ends in $5$, $343 = 7 \times 49$, and $341 = 11 \times 31$.

$347: \text{ odd, digit sum } 14, \text{ not ending in } 0 \text{ or } 5, \quad 18 \times 18 = 324 < 347 < 361 = 19 \times 19$

Test primes up to $18$: $7, 11, 13, 17$ each leave a remainder. So $347$ is prime.

Both numbers in the sum must be prime and add to $48$.

$41 + 7 = 48, \text{ and both } 41 \text{ and } 7 \text{ are prime}$

So $41 + 7$ works. In the others, $24$, $8$, $40$, and $45$ are all composite, so those are not sums of two primes.

Three are prime; one is a perfect square of a prime.

$289 = 17 \times 17$

So $289$ is composite. (It is odd with digit sum $19$, so the rules for $2$ and $3$ miss it; you find $17$ since $17 \times 17 = 289$.) The numbers $193$, $197$, and $199$ are prime.

Work downward from $49$. Note $49 = 7 \times 7$ and $48$ is even.

$47: \text{ odd, digit sum } 11, \text{ not ending in } 0 \text{ or } 5, \quad 7 \times 7 = 49 > 47$

So only $2, 3, 5$ need checking, and none divides $47$. So $47$ is prime, and it is the largest prime below $50$.