What Divisibility Means
For integers \(a\) and \(b\), with \(a\ne0\), the notation \(a\mid b\) means that there is an integer \(k\) such that \(b=ak\). Divisibility is exact integer structure.
Number Theory · Module 1
Divisibility and Prime Factorisation
Definitions, divisibility laws, primes, prime factorisation, divisor counting, GCD and LCM foundations.
Basic Laws
If \(a\mid b\) and \(a\mid c\), then \(a\mid b+c\), \(a\mid b-c\), and more generally \(a\mid xb+yc\) for all integers \(x,y\).
Prime Numbers
A prime number has exactly two positive divisors: \(1\) and itself. The number \(1\) is not prime so that prime factorisation remains unique.
Prime Factorisation
Every integer \(n>1\) has a unique representation \(p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\), where the \(p_i\) are distinct primes.
Counting Divisors
If \(n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\), then \(\tau(n)=(a_1+1)(a_2+1)\cdots(a_m+1)\).
01
If \(6\mid n\), prove \(3\mid n\).
Write \(n=6k=3(2k)\).
02
Find the prime factorisation of \(840\).
\(840=2^3\cdot3\cdot5\cdot7\).
03
Count the divisors of \(840\).
Since \(840=2^3\cdot3\cdot5\cdot7\), the number is \((3+1)(1+1)^3=32\).
04
Find \(\gcd(84,126)\).
\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\), so the GCD is \(42\).
05
Find \(\operatorname{lcm}(84,126)\).
Use maximum exponents: \(2^2\cdot3^2\cdot7=252\).
06
Prove that if \(a\mid b\), then \(a\mid bc\).
If \(b=ak\), then \(bc=a(kc)\).
07
Prove \(a\mid b\) and \(a\mid c\Rightarrow a\mid5b-2c\).
Write \(b=ax\), \(c=ay\), then \(5b-2c=a(5x-2y)\).
08
Find the smallest number using only \(2\) and \(3\) with exactly \(12\) divisors.
Compare exponent patterns. The smallest is \(2^5\cdot3=96\).
09
Show \(n^2-n\) is even.
\(n^2-n=n(n-1)\), a product of consecutive integers.
10
Show \(3\mid n^3-n\).
\(n^3-n=n(n-1)(n+1)\), three consecutive integers.
11
Find primes \(p\) such that \(p,p+2,p+4\) are prime.
Modulo \(3\) shows only \(p=3\) works.
12
List positive divisors of \(24\).
\(1,2,3,4,6,8,12,24\).
13
If \(a\mid b\) and \(b\mid a\), prove \(a=\pm b\).
Use \(b=ak\), \(a=bm\), so \(km=1\).
14
Find the exponent of \(2\) in \(100!\).
\(50+25+12+6+3+1=97\).
15
Explain Euclid’s lemma.
If prime \(p\) appears in \(ab\), it appears in \(a\) or \(b\).
NT-01-001
Exact Division
Divisibility
definition
integer
Decide whether \(8\mid 120\), \(8\mid 122\), and \(9\mid 117\). Explain each answer.
Hint
Use the definition: \(a\mid b\) means \(b=ak\) for some integer \(k\).
Solution
\(120=8\cdot15\), so \(8\mid120\). Since \(122=8\cdot15+2\), \(8\nmid122\). Also \(117=9\cdot13\), so \(9\mid117\).
NT-01-002
Divisibility from a Product
Divisibility
proof
definition
Prove that if \(12\mid n\), then \(3\mid n\).
Hint
Write \(n=12k\).
Solution
If \(12\mid n\), then \(n=12k=3(4k)\) for some integer \(k\). Therefore \(3\mid n\).
NT-01-003
Linear Combination
Divisibility Laws
proof
linear-combination
If \(7\mid a\) and \(7\mid b\), prove that \(7\mid 4a+5b\).
Hint
Set \(a=7x\) and \(b=7y\).
Solution
Let \(a=7x\) and \(b=7y\). Then \(4a+5b=28x+35y=7(4x+5y)\), so \(7\mid4a+5b\).
NT-01-004
Check a Divisibility Claim
Divisibility Laws
proof
difference
If \(11\mid 3x+2\) and \(11\mid x-3\), must \(11\mid 11x-7\)? Give a proof or counterexample.
Hint
Test a value of \(x\) satisfying both given conditions.
Solution
Since \(11\mid3x+2\) and \(11\mid x-3\), any integer linear combination is divisible by \(11\). Now \((3x+2)+8(x-3)=11x-22=11(x-2)\), so it is divisible by \(11\). Also \((11x-7)-(11x-22)=15\), so the original conclusion is not always true. For example, \(x=3\) satisfies \(x-3=0\), but \(3x+2=11\), while \(11x-7=26\) is not divisible by \(11\). Thus the statement is false.
NT-01-005
Prime Factorisation of 420
Prime Factorisation
factorisation
Find the prime factorisation of \(420\).
Hint
Break \(420\) as \(42\cdot10\).
Solution
\(420=42\cdot10=(2\cdot3\cdot7)(2\cdot5)=2^2\cdot3\cdot5\cdot7\).
NT-01-006
Prime Factorisation of 756
Prime Factorisation
factorisation
Find the prime factorisation of \(756\).
Hint
Use \(756=75\cdot10+6\), or divide by \(2\), then by \(3\).
Solution
\(756=2\cdot378=2^2\cdot189=2^2\cdot3^3\cdot7\).
NT-01-007
Counting Divisors
Number of Divisors
divisors
tau-function
How many positive divisors does \(360\) have?
Hint
First write \(360\) as a product of prime powers.
Solution
\(360=2^3\cdot3^2\cdot5\). Therefore \(\tau(360)=(3+1)(2+1)(1+1)=24\).
NT-01-008
A Square with Odd Divisors
Number of Divisors
divisors
squares
Explain why every perfect square has an odd number of positive divisors.
Hint
In a square, all prime exponents are even.
Solution
If \(n=m^2\), then every exponent in the prime factorisation of \(n\) is even. Thus each factor \(a_i+1\) in \(\tau(n)=\prod(a_i+1)\) is odd, and a product of odd numbers is odd.
NT-01-009
GCD from Factorisations
GCD and LCM
gcd
factorisation
Find \(\gcd(144,180)\).
Hint
Use the minimum exponent of each prime.
Solution
\(144=2^4\cdot3^2\) and \(180=2^2\cdot3^2\cdot5\). Hence \(\gcd(144,180)=2^2\cdot3^2=36\).
NT-01-010
LCM from Factorisations
GCD and LCM
lcm
factorisation
Find \(\operatorname{lcm}(144,180)\).
Hint
Use the maximum exponent of each prime.
Solution
Using \(144=2^4\cdot3^2\) and \(180=2^2\cdot3^2\cdot5\), we get \(\operatorname{lcm}(144,180)=2^4\cdot3^2\cdot5=720\).
NT-01-011
Product Formula
GCD and LCM
gcd
lcm
identity
Verify that \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) for \(a=48\), \(b=180\).
Hint
Compute both \(\gcd\) and \(\operatorname{lcm}\).
Solution
\(48=2^4\cdot3\), \(180=2^2\cdot3^2\cdot5\). Thus \(\gcd=2^2\cdot3=12\) and \(\operatorname{lcm}=2^4\cdot3^2\cdot5=720\). Then \(12\cdot720=8640=48\cdot180\).
NT-01-012
Consecutive Product
Divisibility Proofs
consecutive-integers
proof
Prove that \(2\mid n(n+1)\) for every integer \(n\).
Hint
Among two consecutive integers, one is even.
Solution
The integers \(n\) and \(n+1\) are consecutive, so one of them is even. Therefore their product is divisible by \(2\).
NT-01-013
Three Consecutive Integers
Divisibility Proofs
consecutive-integers
proof
Prove that \(3\mid n(n+1)(n+2)\) for every integer \(n\).
Hint
Among any three consecutive integers, one is a multiple of \(3\).
Solution
The integers \(n,n+1,n+2\) cover all possible remainders modulo \(3\). One is divisible by \(3\), so the product is divisible by \(3\).
NT-01-014
Six Divides a Product
Divisibility Proofs
consecutive-integers
proof
Prove that \(6\mid n(n+1)(n+2)\) for every integer \(n\).
Hint
Show divisibility by \(2\) and by \(3\).
Solution
Among three consecutive integers, one is divisible by \(3\), and at least one is even. Since \(2\) and \(3\) are coprime, the product is divisible by \(6\).
NT-01-015
Difference of Squares
Factorisation Methods
factorisation
proof
Prove that if \(a-b\) is divisible by \(5\), then \(a^2-b^2\) is divisible by \(5\).
Hint
Factor \(a^2-b^2\).
Solution
Since \(a^2-b^2=(a-b)(a+b)\), and \(5\mid a-b\), the product \((a-b)(a+b)\) is divisible by \(5\).
NT-01-016
Prime or Composite
Primes
prime
classification
Classify each number as prime or composite: \(37, 49, 57, 83\).
Hint
To test \(n\), check prime divisors up to \(\sqrt n\).
Solution
\(37\) is prime. \(49=7^2\) is composite. \(57=3\cdot19\) is composite. \(83\) is prime because it is not divisible by \(2,3,5,7\), and \(\sqrt{83}<10\).
NT-01-017
Smallest Number with Eight Divisors
Number of Divisors
optimization
divisors
Find the smallest positive integer with exactly \(8\) positive divisors.
Hint
Factor \(8\) as \(8\), \(4\cdot2\), or \(2\cdot2\cdot2\).
Solution
The possible exponent patterns are \(7\), \(3,1\), and \(1,1,1\). The smallest candidates are \(2^7=128\), \(2^3\cdot3=24\), and \(2\cdot3\cdot5=30\). The smallest is \(24\).
NT-01-018
Exactly Nine Divisors
Number of Divisors
optimization
divisors
Find the smallest positive integer with exactly \(9\) positive divisors.
Hint
The exponent patterns come from \(9\) and \(3\cdot3\).
Solution
The patterns are \(8\) and \(2,2\). The smallest candidates are \(2^8=256\) and \(2^2\cdot3^2=36\). Therefore the answer is \(36\).
NT-01-019
A Divisor Equation
Divisibility
equation
divisors
Find all positive integers \(n\) such that \(n\mid 30\).
Hint
List the positive divisors of \(30\).
Solution
Since \(30=2\cdot3\cdot5\), its positive divisors are \(1,2,3,5,6,10,15,30\).
NT-01-020
Dividing a Shifted Expression
Remainders
remainders
expression
If \(n\) leaves remainder \(2\) when divided by \(5\), what remainder does \(3n+1\) leave when divided by \(5\)?
Hint
Write \(n=5k+2\).
Solution
Let \(n=5k+2\). Then \(3n+1=15k+7=5(3k+1)+2\), so the remainder is \(2\).
NT-01-021
Remainder of a Square
Remainders
remainders
squares
Show that the square of an integer leaves remainder \(0\) or \(1\) when divided by \(4\).
Hint
Consider even and odd integers.
Solution
If \(n=2k\), then \(n^2=4k^2\), remainder \(0\). If \(n=2k+1\), then \(n^2=4k^2+4k+1\), remainder \(1\).
NT-01-022
No Square Remainder Two
Remainders
remainders
squares
impossibility
Prove that no integer square can leave remainder \(2\) when divided by \(4\).
Hint
Use the result that square remainders modulo \(4\) are only \(0\) and \(1\).
Solution
From the even/odd cases, every integer square is either \(4k\) or \(4k+1\). Therefore remainder \(2\) is impossible.
NT-01-023
A Prime Divisor
Primes
prime
divisibility
Let \(p\) be prime. If \(p\mid 35\), find all possible values of \(p\).
Hint
Factor \(35\).
Solution
Since \(35=5\cdot7\), the prime divisors of \(35\) are \(5\) and \(7\). Thus \(p\in\{5,7\}\).
NT-01-024
Prime Triple
Primes
prime
remainders
proof
Find all primes \(p\) such that \(p\), \(p+2\), and \(p+4\) are all prime.
Hint
Look at remainders modulo \(3\).
Solution
If \(p>3\), then \(p,p+2,p+4\) are three numbers covering all remainders modulo \(3\), so one is divisible by \(3\). Since it is greater than \(3\), it cannot be prime. Checking \(p=3\), we get \(3,5,7\), all prime. Therefore \(p=3\).
NT-01-025
Factorial Exponent
Prime Factorisation
factorial
exponent
Find the exponent of \(5\) in the prime factorisation of \(50!\).
Hint
Count multiples of \(5\), then extra factors from multiples of \(25\).
Solution
The exponent is \(\left\lfloor50/5\right\rfloor+\left\lfloor50/25\right\rfloor=10+2=12\).
NT-01-026
Trailing Zeros
Prime Factorisation
factorial
trailing-zeros
How many zeros does \(60!\) end with?
Hint
Each trailing zero needs one factor \(10=2\cdot5\). Which prime is rarer?
Solution
The number of trailing zeros is the exponent of \(5\) in \(60!\), since factors of \(2\) are more plentiful. It is \(\lfloor60/5\rfloor+\lfloor60/25\rfloor=12+2=14\).
NT-01-027
A Divisibility Counterexample
Divisibility
counterexample
Is this statement true: if \(a\mid bc\), then \(a\mid b\) or \(a\mid c\)? Give proof or counterexample.
Hint
Try a composite value of \(a\).
Solution
The statement is false. Take \(a=6\), \(b=2\), \(c=3\). Then \(6\mid bc\) because \(bc=6\), but \(6\nmid2\) and \(6\nmid3\).
NT-01-028
Euclid's Lemma Example
Primes
prime
euclid-lemma
Let \(p\) be prime and \(p\mid ab\). Explain why the conclusion \(p\mid a\) or \(p\mid b\) is reasonable using prime factorisation.
Hint
A prime factor appearing in \(ab\) must come from one of the factors.
Solution
In the prime factorisation of \(ab\), all prime factors come from the factorisations of \(a\) and \(b\). If the prime \(p\) appears in \(ab\), it must appear in \(a\) or in \(b\). Thus \(p\mid a\) or \(p\mid b\).
NT-01-029
Coprime Product
GCD and LCM
coprime
divisibility
If \(\gcd(a,b)=1\), \(a\mid n\), and \(b\mid n\), prove that \(ab\mid n\).
Hint
Use prime factorisation: coprime numbers share no prime factors.
Solution
Since \(a\) and \(b\) share no prime factors, the prime powers required by \(a\) and by \(b\) are independent. If \(n\) is divisible by both, then \(n\) contains all prime powers from \(a\) and all from \(b\), so \(ab\mid n\).
NT-01-030
Find the Missing Exponent
Number of Divisors
divisors
exponents
For \(n=2^3\cdot3^a\), find all positive integers \(a\) such that \(n\) has \(20\) positive divisors.
Hint
Use \((3+1)(a+1)=20\).
Solution
\(\tau(n)=(3+1)(a+1)=4(a+1)\). Set \(4(a+1)=20\), so \(a+1=5\) and \(a=4\).
NT-01-031
Shared Divisors
GCD and LCM
gcd
divisors
How many positive common divisors do \(84\) and \(126\) have?
Hint
Common divisors are exactly the divisors of the \(\gcd\).
Solution
\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\), so \(\gcd(84,126)=2\cdot3\cdot7=42\). Since \(42=2\cdot3\cdot7\), it has \((1+1)^3=8\) positive divisors.
NT-01-032
All Divisors from Exponents
Prime Factorisation
divisors
listing
List all positive divisors of \(2^2\cdot3\).
Hint
Choose the exponent of \(2\) from \(0,1,2\) and of \(3\) from \(0,1\).
Solution
The number is \(12\). Its positive divisors are \(1,2,3,4,6,12\).
NT-01-033
Divisibility by Nine
Divisibility Tests
divisibility-test
digits
Use the digit-sum test to decide whether \(738\) is divisible by \(9\).
Hint
Add the digits.
Solution
The digit sum is \(7+3+8=18\), and \(9\mid18\). Therefore \(9\mid738\).
NT-01-034
Make It Divisible
Divisibility Tests
digits
divisibility-test
Find all digits \(x\) such that the number \(45x2\) is divisible by \(3\).
Hint
A number is divisible by \(3\) when its digit sum is divisible by \(3\).
Solution
The digit sum is \(4+5+x+2=11+x\). We need \(11+x\equiv0\pmod3\). Since \(11\equiv2\pmod3\), \(x\equiv1\pmod3\). The possible digits are \(1,4,7\).
NT-01-035
Even Divisors
Number of Divisors
divisors
counting
How many positive even divisors does \(720\) have?
Hint
First factor \(720\). For an even divisor, the exponent of \(2\) must be at least \(1\).
Solution
\(720=2^4\cdot3^2\cdot5\). An even divisor has exponent of \(2\) equal to \(1,2,3,\) or \(4\): \(4\) choices. The exponent of \(3\) has \(3\) choices and of \(5\) has \(2\) choices. Total: \(4\cdot3\cdot2=24\).
NT-01-036
Odd Divisors
Number of Divisors
divisors
counting
How many positive odd divisors does \(720\) have?
Hint
Odd divisors use no factor \(2\).
Solution
Since \(720=2^4\cdot3^2\cdot5\), an odd divisor must use \(2^0\). Then the exponent of \(3\) has \(3\) choices and the exponent of \(5\) has \(2\) choices. There are \(3\cdot2=6\) positive odd divisors.
NT-01-037
A Divisibility Chain
Divisibility
proof
transitivity
Prove that if \(a\mid b\) and \(b\mid c\), then \(a\mid c\).
Hint
Write \(b=ak\) and \(c=bm\).
Solution
If \(a\mid b\), then \(b=ak\). If \(b\mid c\), then \(c=bm\). Therefore \(c=akm=a(km)\), so \(a\mid c\).
NT-01-038
Mutual Divisibility
Divisibility
proof
absolute-value
Let \(a\) and \(b\) be positive integers. Prove that if \(a\mid b\) and \(b\mid a\), then \(a=b\).
Hint
Use \(b=ak\) and compare sizes.
Solution
Since \(a\mid b\), write \(b=ak\) for a positive integer \(k\). Since \(b\mid a\), write \(a=bm\) for a positive integer \(m\). Then \(a=akm\). Because \(a>0\), we get \(km=1\), so \(k=m=1\), and \(a=b\).
NT-01-039
Find the GCD and LCM
GCD and LCM
gcd
lcm
Find \(\gcd(210,330)\) and \(\operatorname{lcm}(210,330)\).
Hint
Factor both numbers first.
Solution
\(210=2\cdot3\cdot5\cdot7\), and \(330=2\cdot3\cdot5\cdot11\). Therefore \(\gcd=2\cdot3\cdot5=30\), and \(\operatorname{lcm}=2\cdot3\cdot5\cdot7\cdot11=2310\).
NT-01-040
Olympiad Warm-Up
Divisibility Proofs
proof
factorisation
consecutive-integers
Prove that \(24\mid n(n^2-1)(n+2)\) for every integer \(n\).
Hint
Factor the expression into four consecutive integers.
Solution
We have \(n(n^2-1)(n+2)=n(n-1)(n+1)(n+2)\), the product of four consecutive integers. Among four consecutive integers there is a multiple of \(4\), another even number, and at least one multiple of \(3\). Thus the product is divisible by \(8\cdot3=24\).
No problems found.
Worksheet
Printable PDF and DOCX worksheets will be attached here.