9. Number properties
Primes, divisibility, remainders, units-digit cycles. Remainders cycle with a period.
Core ideas
- A prime has exactly two factors; 2 is the only even prime, and 1 is not prime.
- Remainders behave under arithmetic: if n leaves remainder r when divided by d, then kn leaves the same remainder as kr, and n + m leaves the same remainder as r + (m's remainder).
- Units digits cycle with short periods (7 cycles 7, 9, 3, 1 with period 4); reduce the exponent mod the cycle length, and remainder 0 means the LAST digit in the cycle.
- Divisibility questions are prime-factorization questions: n is divisible by k when n's prime factorization contains k's.
Worked example 1
When positive integer n is divided by 7, the remainder is 5. What is the remainder when 3n + 4 is divided by 7?
Show solution
Work with the remainder directly: 3n behaves like 3 * 5 = 15, and 15 divided by 7 leaves remainder 1. Then 3n + 4 behaves like 1 + 4 = 5. Check with n = 5: 3(5) + 4 = 19 = 2 * 7 + 5. Remainder 5.
Worked example 2
What is the units digit of 7^43?
Show solution
Powers of 7 have units digits cycling 7, 9, 3, 1 with period 4. Divide the exponent by 4: 43 = 4 * 10 + 3, remainder 3. Remainder 3 means the third digit in the cycle, which is 3. So the units digit of 7^43 is 3.
Practice set
Question 1
What is the units digit of 7^25?
The units digits of powers of 7 repeat in a short cycle; find where 25 lands.
The units digits of powers of 7 cycle with period 4: 7, 9, 3, 1. Since 25 = 4 x 6 + 1, 7^25 lands on the first position of the cycle, so its units digit is 7.
Question 2
What is the remainder when 3^100 is divided by 5?
Track the remainders of successive powers of 3 mod 5; they cycle.
The remainders of 3^1, 3^2, 3^3, 3^4 when divided by 5 are 3, 4, 2, 1, and then the pattern repeats with period 4. Since 100 is a multiple of 4, 3^100 lands on the last position of the cycle, giving remainder 1.
Question 3
How many multiples of 3 are there from 100 to 300 inclusive?
Find the first and last multiples in the range, then count with (last - first)/3 + 1.
The first multiple of 3 at or above 100 is 102, and the last at or below 300 is 300. The count is (300 - 102)/3 + 1 = 66 + 1 = 67.
Question 4
If n is a positive integer and n^2 is divisible by 72, what is the largest positive integer that must divide n?
Factor 72 into primes and ask what each prime forces on n itself, not on n^2.
72 = 2^3 x 3^2. For n^2 to contain 2^3, n must contain at least 2^2 (since exponents in n^2 are doubled, n with only 2^1 gives 2^2, not enough). For n^2 to contain 3^2, n needs at least 3^1. So n must be divisible by 4 x 3 = 12. And n = 12 works, since 144 = 72 x 2, so nothing larger is guaranteed.