Exercises — Prime numbers — Sieve of Eratosthenes, primality testing

Apply the definition: a prime has exactly two distinct divisors, $1$ and itself.

• $1$ → only one divisor. Neither prime nor composite.
• $2$ → divisors $1,2$. Prime (the only even prime).
• $9=3\times 3$ → divisor $3$. Composite.
• $17$ → $\sqrt{17}\approx 4.1$; test $2,3$: odd, and $1+7=8$ not divisible by $3$. Prime.
• $21=3\times 7$ → Composite. Primes: $\{2,17\}$.

Walk upward from $51$:

• $51=3\times 17$ (digit sum $6$, divisible by $3$).
• $52$ even. $53$: $\sqrt{53}\approx 7.3$, test $2,3,5,7$ → none divide. $53$ is prime. Answer: $53$.

WHY ​: if $211=a\times b$ with $a\le b$, then $a\le \sqrt{211}\approx 14.5$. So a divisor above $14$ always has a partner below $14$ — testing up to $14$ is enough. Test primes $\le 14$: $2,3,5,7,11,13$.

• $2$: $211$ is odd. No.
• $3$: digit sum $2+1+1=4$, not a multiple of $3$. No.
• $5$: ends in $1$. No.
• $7$: $7\times 30=210$, remainder $1$. No.
• $11$: alternating sum $2-1+1=2$, not $0$ or $11$. No.
• $13$: $13\times 16=208$, remainder $3$. No. No divisor $\le 14$ ⇒ $211$ is prime. ✓

$\sqrt{20}\approx 4.47$, so we only sieve with primes $p$ where $p^2\le 20$, i.e. $p=2,3$.

• $p=2$: cross from $2^2=4$: $4,6,8,10,12,14,16,18,20$.
• $p=3$: cross from $3^2=9$: $9,12,15,18$ (some already gone — that's fine).
• $p=5$: $5^2=25>20$ → stop. Survivors: $\boxed{2,3,5,7,11,13,17,19}$ — the $8$ primes below $20$. ✓

Look at the figure: the yellow curve is $y=\sqrt{n}$ area line; the dashed diagonal marks where $a=b=\sqrt{36}=6$. Every factor pair $(a,b)$ with $a\le b$ sits with $a$ to the left of $6$ and $b$ to the right. The pairs mirror around $6$. Factor pairs of $36$: $1\times 36,2\times 18,3\times 12,4\times 9,6\times 6.$ The smaller entries are $1,2,3,4,6$ — all $\le \sqrt{36}=6$. Every larger factor ($9,12,18,36$) is just the partner of a smaller one already found. So scanning past $6$ re-discovers nothing new. That is exactly why trial division stops at $\lfloor \sqrt{n}\rfloor$. ✓

A composite survives "$2,3,5$" only if its smallest prime factor is $\ge 7$. The smallest such number is $7\times 7=49$. Check it dodges the partial test:

• $49$ is odd ⇒ passes "$2$".
• digit sum $4+9=13$, not a multiple of $3$ ⇒ passes "$3$".
• ends in $9$ ⇒ passes "$5$". Yet $49=7^2$ is composite. Any smaller composite ($\le 48$) has a factor of $2,3,$ or $5$ and would be caught. Answer: $49$. ✓

Compute the raw values: $A=105$, $B=385$. By the Fundamental Theorem of Arithmetic, each number is a unique bag of prime factors: $A=3^1{5}^1{7}^1,B=5^1{7}^{1}11^1.$

• GCD = product of primes in both bags, each to the smaller power: common primes are $5,7$ ⇒ $\gcd (A,B)=5\times 7=35.$
• LCM = every prime that appears in either bag, each to the larger power: $3,5,7,11$ ⇒ $\mathrm{lcm}(A,B)=3\times 5\times 7\times 11=1155.$ Sanity check: $\gcd \times \mathrm{lcm}=35\times 1155=40425=105\times 385=A\times B$. ✓

Starting at $2p=14$ we would visit multiples $14,21,28,\dots$ up to $p^2=49$ (exclusive) before reaching the first genuinely-new one. These are $7k$ for $k=2,3,4,5,6$: that's $14,21,28,35,42$ — 5 multiples. Every one was already crossed by a smaller prime ($2,3,5$), so all $5$ crossings are wasted. Correct start is $p^2=49$; the first new multiple is $49=7\times 7$. Wasted crossings avoided for $p=7$: $5$. ✓ (This is the general saving: $p-2$ redundant multiples per prime.)

First, the boundary $k=2$. $R_2=11$ is prime — so the claim is deliberately stated for $k\ge 4$, not all even $k$. We exclude $k=2$ on purpose because it is the one even repunit that stays prime. Keep this in mind: "even $k$" alone is not enough; we need $k\ge 4$.

Now the main case, $k\ge 4$ even. Write $k=2m$ with $m\ge 2$. The trick is to read the string of ones two digits at a time from the right, because $11$ is itself two ones.

Deriving the grouping concretely. Take $R_4=1111$. Split it into two-digit blocks from the right: $\underline{11}\underline{11}$. The left block sits in the "hundreds" place, so its value is $11\times 100$; the right block is just $11$. Hence $R_4=11\times 100+11=11(100+1)=11\times 101.$ For $R_6=111111$ the same splitting gives three blocks: $R_6=11\times 100^2+11\times 100^1+11\times 100^0=11(100^2+100+1).$ In general, grouping $R_{2m}$ into $m$ two-digit blocks $\underline{11}\underline{11}\cdots \underline{11}$, block number $j$ (counting from the right, $j=0,1,\dots ,m-1$) carries the value $11\times 100^j$. Adding the blocks: $R_{2m}=11(1+100+100^2+\cdots +100^{m-1}).$ This factorisation is not "asserted from grouping" — it is exactly the place-value expansion, where each two-digit block of ones is worth $11$ scaled by a power of $100$.

Conclusion. The bracket $(1+100+\cdots +100^{m-1})$ is a whole number and, since $m\ge 2$, it is at least $1+100=101>1$. So $R_{2m}=11\times (\text{something}\ge 101)$ is a product of two factors each bigger than $1$ ⇒ $R_{2m}$ is composite for every even $k=2m\ge 4$. ✓ Example check: $R_4=1111=11\times 101$; $R_6=111111=11\times 10101$. Both composite.

Numbers ending in $0,2,4,5,6,8$ are handled by divisibility by $2$ or $5$, so the interesting last digits are exactly $1,3,7,9$. For each we must show both outcomes are possible — the last digit alone decides nothing.

Every one of the four ending-digit cases produces both a composite and a prime ⇒ the last digit carries no primality information. The claim is false. ✓

$\sqrt{2003}\approx 44.75$, so the largest divisor to test is $\lfloor \sqrt{2003}\rfloor =44$; the largest prime $\le 44$ is $43$. Test primes $2,3,5,7,11,13,17,19,23,29,31,37,41,43$:

• even? no. digit sum $2+0+0+3=5$, not $÷3$. ends in $3$, not $÷5$.
• $7$: $7\times 286=2002$, rem $1$. $11$: alt sum $3-0+0-2=1$, no. $13$: $13\times 154=2002$, rem $1$. $17$: $17\times 117=1989$, rem $14$. $19$: $19\times 105=1995$, rem $8$. $23$: $23\times 87=2001$, rem $2$. $29$: $29\times 69=2001$, rem $2$. $31$: $31\times 64=1984$, rem $19$. $37$: $37\times 54=1998$, rem $5$. $41$: $41\times 48=1968$, rem $35$. $43$: $43\times 46=1978$, rem $25$. No prime $\le 43$ divides $2003$ ⇒ $2003$ is prime. ✓ Largest prime tested: $43$.

• Prime = exactly two divisors; $1$ is neither.
• Trial-divide only up to $\lfloor \sqrt{n}\rfloor$ — the small factor always hides below the square root.
• Sieve: cross multiples from $p^2$, stop when $p^2>N$.
• Factorisation is unique ⇒ GCD uses smaller exponents, LCM uses larger.
• Last digit alone never decides primality; and "even $k$" repunits are composite only from $k\ge 4$.