Module 1
A bilingual course system for serious problem solving.
Number Theory starts with divisibility, primes, factorisation, and proof habits.
Module 1
NT-01-001
Divisibility
Decide whether \(8\mid 120\), \(8\mid 122\), and \(9\mid 117\). Explain each answer.
Use the definition: \(a\mid b\) means \(b=ak\) for some integer \(k\).
\(120=8\cdot15\), so \(8\mid120\). Since \(122=8\cdot15+2\), \(8\nmid122\). Also \(117=9\cdot13\), so \(9\mid117\).
NT-01-002
Divisibility
Prove that if \(12\mid n\), then \(3\mid n\).
Write \(n=12k\).
If \(12\mid n\), then \(n=12k=3(4k)\) for some integer \(k\). Therefore \(3\mid n\).
NT-01-003
Divisibility Laws
If \(7\mid a\) and \(7\mid b\), prove that \(7\mid 4a+5b\).
Set \(a=7x\) and \(b=7y\).
Let \(a=7x\) and \(b=7y\). Then \(4a+5b=28x+35y=7(4x+5y)\), so \(7\mid4a+5b\).
NT-01-004
Divisibility Laws
If \(11\mid 3x+2\) and \(11\mid x-3\), must \(11\mid 11x-7\)? Give a proof or counterexample.
Test a value of \(x\) satisfying both given conditions.
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
Find the prime factorisation of \(420\).
Break \(420\) as \(42\cdot10\).
\(420=42\cdot10=(2\cdot3\cdot7)(2\cdot5)=2^2\cdot3\cdot5\cdot7\).
NT-01-006
Prime Factorisation
Find the prime factorisation of \(756\).
Use \(756=75\cdot10+6\), or divide by \(2\), then by \(3\).
\(756=2\cdot378=2^2\cdot189=2^2\cdot3^3\cdot7\).
NT-01-007
Number of Divisors
How many positive divisors does \(360\) have?
First write \(360\) as a product of prime powers.
\(360=2^3\cdot3^2\cdot5\). Therefore \(\tau(360)=(3+1)(2+1)(1+1)=24\).
NT-01-008
Number of Divisors
Explain why every perfect square has an odd number of positive divisors.
In a square, all prime exponents are even.
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 and LCM
Find \(\gcd(144,180)\).
Use the minimum exponent of each prime.
\(144=2^4\cdot3^2\) and \(180=2^2\cdot3^2\cdot5\). Hence \(\gcd(144,180)=2^2\cdot3^2=36\).
NT-01-010
GCD and LCM
Find \(\operatorname{lcm}(144,180)\).
Use the maximum exponent of each prime.
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
GCD and LCM
Verify that \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) for \(a=48\), \(b=180\).
Compute both \(\gcd\) and \(\operatorname{lcm}\).
\(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
Divisibility Proofs
Prove that \(2\mid n(n+1)\) for every integer \(n\).
Among two consecutive integers, one is even.
The integers \(n\) and \(n+1\) are consecutive, so one of them is even. Therefore their product is divisible by \(2\).
NT-01-013
Divisibility Proofs
Prove that \(3\mid n(n+1)(n+2)\) for every integer \(n\).
Among any three consecutive integers, one is a multiple of \(3\).
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
Divisibility Proofs
Prove that \(6\mid n(n+1)(n+2)\) for every integer \(n\).
Show divisibility by \(2\) and by \(3\).
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
Factorisation Methods
Prove that if \(a-b\) is divisible by \(5\), then \(a^2-b^2\) is divisible by \(5\).
Factor \(a^2-b^2\).
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
Primes
Classify each number as prime or composite: \(37, 49, 57, 83\).
To test \(n\), check prime divisors up to \(\sqrt n\).
\(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
Number of Divisors
Find the smallest positive integer with exactly \(8\) positive divisors.
Factor \(8\) as \(8\), \(4\cdot2\), or \(2\cdot2\cdot2\).
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
Number of Divisors
Find the smallest positive integer with exactly \(9\) positive divisors.
The exponent patterns come from \(9\) and \(3\cdot3\).
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
Divisibility
Find all positive integers \(n\) such that \(n\mid 30\).
List the positive divisors of \(30\).
Since \(30=2\cdot3\cdot5\), its positive divisors are \(1,2,3,5,6,10,15,30\).
NT-01-020
Remainders
If \(n\) leaves remainder \(2\) when divided by \(5\), what remainder does \(3n+1\) leave when divided by \(5\)?
Write \(n=5k+2\).
Let \(n=5k+2\). Then \(3n+1=15k+7=5(3k+1)+2\), so the remainder is \(2\).
NT-01-021
Remainders
Show that the square of an integer leaves remainder \(0\) or \(1\) when divided by \(4\).
Consider even and odd integers.
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
Remainders
Prove that no integer square can leave remainder \(2\) when divided by \(4\).
Use the result that square remainders modulo \(4\) are only \(0\) and \(1\).
From the even/odd cases, every integer square is either \(4k\) or \(4k+1\). Therefore remainder \(2\) is impossible.
NT-01-023
Primes
Let \(p\) be prime. If \(p\mid 35\), find all possible values of \(p\).
Factor \(35\).
Since \(35=5\cdot7\), the prime divisors of \(35\) are \(5\) and \(7\). Thus \(p\in\{5,7\}\).
NT-01-024
Primes
Find all primes \(p\) such that \(p\), \(p+2\), and \(p+4\) are all prime.
Look at remainders modulo \(3\).
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
Prime Factorisation
Find the exponent of \(5\) in the prime factorisation of \(50!\).
Count multiples of \(5\), then extra factors from multiples of \(25\).
The exponent is \(\left\lfloor50/5\right\rfloor+\left\lfloor50/25\right\rfloor=10+2=12\).
NT-01-026
Prime Factorisation
How many zeros does \(60!\) end with?
Each trailing zero needs one factor \(10=2\cdot5\). Which prime is rarer?
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
Divisibility
Is this statement true: if \(a\mid bc\), then \(a\mid b\) or \(a\mid c\)? Give proof or counterexample.
Try a composite value of \(a\).
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
Primes
Let \(p\) be prime and \(p\mid ab\). Explain why the conclusion \(p\mid a\) or \(p\mid b\) is reasonable using prime factorisation.
A prime factor appearing in \(ab\) must come from one of the factors.
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
GCD and LCM
If \(\gcd(a,b)=1\), \(a\mid n\), and \(b\mid n\), prove that \(ab\mid n\).
Use prime factorisation: coprime numbers share no prime factors.
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
Number of Divisors
For \(n=2^3\cdot3^a\), find all positive integers \(a\) such that \(n\) has \(20\) positive divisors.
Use \((3+1)(a+1)=20\).
\(\tau(n)=(3+1)(a+1)=4(a+1)\). Set \(4(a+1)=20\), so \(a+1=5\) and \(a=4\).
NT-01-031
GCD and LCM
How many positive common divisors do \(84\) and \(126\) have?
Common divisors are exactly the divisors of the \(\gcd\).
\(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
Prime Factorisation
List all positive divisors of \(2^2\cdot3\).
Choose the exponent of \(2\) from \(0,1,2\) and of \(3\) from \(0,1\).
The number is \(12\). Its positive divisors are \(1,2,3,4,6,12\).
NT-01-033
Divisibility Tests
Use the digit-sum test to decide whether \(738\) is divisible by \(9\).
Add the digits.
The digit sum is \(7+3+8=18\), and \(9\mid18\). Therefore \(9\mid738\).
NT-01-034
Divisibility Tests
Find all digits \(x\) such that the number \(45x2\) is divisible by \(3\).
A number is divisible by \(3\) when its digit sum is divisible by \(3\).
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
Number of Divisors
How many positive even divisors does \(720\) have?
First factor \(720\). For an even divisor, the exponent of \(2\) must be at least \(1\).
\(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
Number of Divisors
How many positive odd divisors does \(720\) have?
Odd divisors use no factor \(2\).
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
Divisibility
Prove that if \(a\mid b\) and \(b\mid c\), then \(a\mid c\).
Write \(b=ak\) and \(c=bm\).
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
Divisibility
Let \(a\) and \(b\) be positive integers. Prove that if \(a\mid b\) and \(b\mid a\), then \(a=b\).
Use \(b=ak\) and compare sizes.
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
GCD and LCM
Find \(\gcd(210,330)\) and \(\operatorname{lcm}(210,330)\).
Factor both numbers first.
\(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
Divisibility Proofs
Prove that \(24\mid n(n^2-1)(n+2)\) for every integer \(n\).
Factor the expression into four consecutive integers.
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.