A brief note on Division, Divisibility Rules and Primes . Try each question before you open its answer.
The key facts Division algorithm: for b > 0 b > 0 b > 0 , a = b q + r a = bq + r a = b q + r with 0 ≤ r < b 0 \le r < b 0 ≤ r < b , in exactly one way. Divisibility: b ∣ a b \mid a b ∣ a means a = b k a = bk a = bk . If d ∣ a d \mid a d ∣ a and d ∣ b d \mid b d ∣ b , then d ∣ a x + b y d \mid ax + by d ∣ a x + b y . Cases: every integer is 3 k 3k 3 k , 3 k + 1 3k + 1 3 k + 1 or 3 k + 2 3k + 2 3 k + 2 . A square leaves 0 0 0 or 1 1 1 on division by 3 3 3 and by 4 4 4 . Consecutive integers: the product of k k k of them is divisible by k ! k! k ! . Factorisations: a − b ∣ a n − b n a - b \mid a^n - b^n a − b ∣ a n − b n ; for odd n n n , a + b ∣ a n + b n a + b \mid a^n + b^n a + b ∣ a n + b n . Digit rules: digit sum for 3 3 3 and 9 9 9 , alternating sum for 11 11 11 , last k k k digits for 2 k 2^k 2 k and 5 k 5^k 5 k , groups of three for 7 7 7 , 11 11 11 , 13 13 13 . Primes: a composite n n n has a prime factor at most n \sqrt{n} n ; there are infinitely many primes. Euclid's lemma: if p ∣ a b p \mid ab p ∣ ab , then p ∣ a p \mid a p ∣ a or p ∣ b p \mid b p ∣ b . Fundamental theorem: n = p 1 a 1 ⋯ p k a k n = p_1^{a_1} \cdots p_k^{a_k} n = p 1 a 1 ⋯ p k a k in one way only. A k k k th power has every exponent a multiple of k k k . Practise with new numbers
A program to try The program tests four facts of this note on many numbers.
Read it first. Then run it. Does each line print what the note says?
1. Change n = 5831 to a number of your own. Do the two remainders still agree?
Mistakes to avoid A negative remainder. The remainder is always between 0 0 0 and b − 1 b - 1 b − 1 . Joining divisors that share a factor. 4 ∣ a 4 \mid a 4 ∣ a and 6 ∣ a 6 \mid a 6 ∣ a give only 12 ∣ a 12 \mid a 12 ∣ a . Splitting a composite divisor of a product. Only a prime can be split by Euclid's lemma. Calling 1 a prime. A pattern is not a proof. Check every case, or give an argument. Check yourself Find the remainder of − 38 -38 − 38 on division by 6 6 6 . Stuck? Show a hint Show the answerShow that n 2 + n n^2 + n n 2 + n is even for every integer n n n . Stuck? Show a hint Show the answerIs 7 × 11 × 13 × 2 + 1 7 \times 11 \times 13 \times 2 + 1 7 × 11 × 13 × 2 + 1 divisible by 7 7 7 ? Stuck? Show a hint Show the answerFind the digit d d d for which 38 d 2 ‾ \overline{38d2} 38 d 2 is divisible by 11 11 11 . Stuck? Show a hint Show the answerWrite 2 6 − 1 2^6 - 1 2 6 − 1 as a product of primes. Stuck? Show a hint Show the answerSources David M. Burton, Elementary Number Theory , Chapters 2 and 3. NCERT, Mathematics Textbook for Class X, Chapter 1 (Real Numbers).