Maths WorkshopMaths problems with full solutions
Exercise 989Combinatorics › Inclusion-exclusionL1Added 3 Nov 2026

Numbers coprime to $30$ up to $100$

#IE#coprime#totient

Statement

How many integers from 11 to 100100 are coprime to 3030?

Hint

IE on divisibility by 22, 33, 55.

Show solutionHide solution

Solution

From earlier. Numbers divisible by 22, 33, or 55: 7474.

Complement. 100−74=26100-74=26.

Conclusion. 2626 integers are coprime to 3030.

Check. Pattern period 3030: φ(30)=8\varphi(30)=8 per period; 100=3⋅30+10100=3\cdot30+10. In each full period 88, so 2424; in the last 1010, coprime to 3030: 1,7,11,13,17,19,23,291,7,11,13,17,19,23,29 — but only 1,71,7 are ≤10\le10. So 24+2=2624+2=26. ✓