Number System — CDS Elementary Mathematics

Formulas (5)

• The division algorithm · Division algorithm
  $$N = d\,q + r, \qquad 0 \le r < d$$
• The square of an odd number leaves remainder 1 on division by 8 · Odd square modulo 8
  $$m \text{ odd} \;\Longrightarrow\; m^2 = 8n+1 \quad\text{i.e.}\quad m^2 \equiv 1 \pmod 8$$
• A product of consecutive integers is divisible by the factorial of how many there are · Consecutive-run divisibility
  $$k! \;\big|\; n(n+1)(n+2)\cdots(n+k-1)$$
• Centring a run of consecutive integers on its middle term · Sum of squares of three consecutive integers
  $$(n-1)^2 + n^2 + (n+1)^2 = 3n^2 + 2$$
• Using the parity of a total to count the odd terms · Sum of parity signs
  $$\sum_{i=1}^{k} (-1)^{a_i} = k - 2j \quad (j = \text{how many } a_i \text{ are odd})$$

Reference tables (2)

Watch out for (10)

• A remainder can never equal or exceed the divisor
  → The division algorithm
• An even product does not mean both factors are even
  → Parity bookkeeping for sums and products
• A statement about parity often says nothing about the variable you want
  → Parity bookkeeping for sums and products
• Remainder 1 modulo 8 is a stronger claim than remainder 1 modulo 4
  → The square of an odd number leaves remainder 1 on division by 8
• The rule is for ODD bases only
  → The square of an odd number leaves remainder 1 on division by 8
• The rule gives a guarantee, not the largest divisor
  → A product of consecutive integers is divisible by the factorial of how many there are
• What is true for three consecutive integers is not true for four
  → Centring a run of consecutive integers on its middle term
• Count the values that are ATTAINABLE, not the cases that are arithmetically allowed
  → Using the parity of a total to count the odd terms
• In data sufficiency, insufficient plus insufficient is not always sufficient
  → The three statement formats CDS uses, and how to attack each
• A statement question is not an all-or-nothing question
  → The three statement formats CDS uses, and how to attack each

Formulas (8)

• Writing a number in expanded algebraic form · Expanded form
  $$\overline{ab} = 10a+b, \qquad \overline{abc} = 100a+10b+c$$
• Reversing a two-digit number: the 11 and 9 identities · Reversal sum and difference
  $$N+N' = 11(a+b), \qquad N-N' = 9(a-b)$$
• Reversing a three-digit number and swapping just two digits · Three-digit reversal difference
  $$\overline{XYZ} - \overline{ZYX} = 99\,(X-Z)$$
• The cyclic sum of a three-digit number is 111 times its digit sum · Cyclic sum identity
  $$\overline{XYZ} + \overline{YZX} + \overline{ZXY} = 111\,(X+Y+Z)$$
• Numbers built by repeating a block of digits · Repeated-block constants
  $$\overline{abcabc} = \overline{abc}\times 1001, \qquad \overline{XYXYXY} = \overline{XY}\times 10101$$
• Strings of repeated ones and nines · Repunit closed form
  $$R_n = \underbrace{11\cdots1}_{n\text{ ones}} = \frac{10^{n}-1}{9}$$
• Only the last few digits decide the last few digits · Last k digits
  $$\text{last } k \text{ digits of } AB \;=\; (A \bmod 10^{k})(B \bmod 10^{k}) \bmod 10^{k}$$
• Solving equations whose unknowns are single digits · Complement trick for near-round multipliers
  $$999 \times n = 1000n - n, \qquad 99 \times n = 100n - n$$

Watch out for (10)

• The digit constraints are part of the problem, not an afterthought
  → Writing a number in expanded algebraic form
• Decide which way the difference runs before using it
  → Reversing a two-digit number: the 11 and 9 identities
• A difference that is not a multiple of 9 means no such number exists
  → Reversing a two-digit number: the 11 and 9 identities
• 99, 90 and 9 are three different swaps
  → Reversing a three-digit number and swapping just two digits
• Divisible by 3 does not upgrade to divisible by 9
  → The cyclic sum of a three-digit number is 111 times its digit sum
• 1001 and 10101 factorise differently
  → Numbers built by repeating a block of digits
• A repunit is not a power of ten
  → Strings of repeated ones and nines
• Keep as many digits as the question asks for, and no fewer
  → Only the last few digits decide the last few digits
• Hundreds place is not the hundredth digit
  → Only the last few digits decide the last few digits
• Maximising one digit means minimising the others, within bounds
  → Solving equations whose unknowns are single digits

Formulas (3)

• Recovering a hidden digit from a divisibility condition · Hidden-digit condition
  $$P \equiv -\!\!\sum(\text{known digits}) \pmod{9}, \qquad 0 \le P \le 9$$
• Divisors for which only the tail of the number matters · Tail rule
  $$N \equiv \left(N \bmod 10^{k}\right) \pmod{2^{k}} \quad\text{and}\quad \pmod{5^{k}}$$
• What to do when the divisor has no usable test · The 1001 grouping fact
  $$1001 = 7 \times 11 \times 13$$

Reference tables (1)

Watch out for (7)

• The smallest odd composite number is 9, not 1, 3 or 15
  → The divisibility test table
• For a composite divisor, split into COPRIME parts
  → The divisibility test table
• A mod-9 condition often has TWO digit solutions, not one
  → Recovering a hidden digit from a divisibility condition
• With two hidden digits the condition fixes only their SUM
  → Recovering a hidden digit from a divisibility condition
• The tail rule works only for divisors built from 2s and 5s
  → Divisors for which only the tail of the number matters
• Reading the tail of a described number is where this goes wrong
  → Divisors for which only the tail of the number matters
• Trial is the intended method here, so do not hunt for a rule
  → What to do when the divisor has no usable test

Formulas (4)

• Reducing the exponent modulo 4 · Exponent reduction
  $$b^{n} \text{ ends in the } r\text{-th cycle entry}, \quad r = n \bmod 4 \;\;(r=0 \Rightarrow \text{4th entry})$$
• Unit digits of sums, differences and products of powers · Unit digit of a combination
  $$(A \pm B) \bmod 10 = \big[(A \bmod 10) \pm (B \bmod 10)\big] \bmod 10$$
• A number that is odd and a multiple of 5 must end in 5 · Odd multiple of five
  $$5 \mid N \;\text{and}\; N \text{ odd} \;\Longrightarrow\; N \equiv 5 \pmod{10}$$
• Counting how many unit digits an expression can produce · Number of cases to check
  $$\text{cases} = \prod_{\text{moving terms}} (\text{period of that term})$$

Reference tables (1)

Watch out for (8)

• The base's other digits are irrelevant, and the exponent's are not
  → The unit-digit cycle of each base
• A remainder of 0 sends you to the END of the cycle, not the start
  → Reducing the exponent modulo 4
• Reduce the exponent modulo 4, never modulo 10
  → Reducing the exponent modulo 4
• Factor a difference of powers before taking unit digits
  → Unit digits of sums, differences and products of powers
• A negative difference needs plus 10, not a minus sign
  → Unit digits of sums, differences and products of powers
• The word ODD in the question is what changes the answer from 0 to 5
  → A number that is odd and a multiple of 5 must end in 5
• Collapse the period-1 terms before you start enumerating
  → Counting how many unit digits an expression can produce
• The question asks for a COUNT, or sometimes for a SUM of the distinct values
  → Counting how many unit digits an expression can produce

Formulas (4)

• Testing a number for primality by trial division · Trial-division bound
  $$n \text{ is prime} \iff p \nmid n \ \text{ for every prime } p \le \sqrt{n}$$
• Forcing a prime to be 2 with a parity argument · The forcing rule
  $$p+q \text{ odd (with } p,q \text{ prime)} \;\Longrightarrow\; \{p,q\} \ni 2$$
• Coprimality and Euclid's lemma · Coprimality via the difference
  $$\gcd(n,\,n+1)=1 \quad\text{for every integer } n$$
• Breaking a number into its prime factors · Unique factorisation
  $$N = p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k} \quad\text{uniquely}$$

Reference tables (2)

Watch out for (6)

• Coprime does not mean prime
  → Primes, composites, and the numbers that are neither
• Numbers near 400 or 1000 look prime and often are not
  → Testing a number for primality by trial division
• Having forced the 2, still check the survivor is prime
  → Forcing a prime to be 2 with a parity argument
• Euclid's lemma needs the divisor to be PRIME
  → Coprimality and Euclid's lemma
• The converse of a true statement about primes is usually false
  → Forms that look like they generate primes but do not
• The LCM of two distinct primes is their product
  → Breaking a number into its prime factors

Formulas (6)

• Canonical prime-power form · Canonical form
  $$N = p_1^{a_1}\,p_2^{a_2}\cdots p_k^{a_k}$$
• Counting the divisors of a number · Divisor count
  $$d(N)=\prod_{i=1}^{k}(a_i+1)$$
• Summing the divisors of a number · Divisor sum
  $$\sigma(N)=\prod_{i=1}^{k}\frac{p_i^{a_i+1}-1}{p_i-1}$$
• Odd divisors, divisors of a square, and working backwards · Divisors of a square
  $$d(N^{2})=\prod_{i=1}^{k}(2a_i+1)$$
• Counting the zeros at the end of a factorial · Zeros at the end of n factorial
  $$Z(n!)=\sum_{i\ge 1}\left\lfloor \frac{n}{5^{i}}\right\rfloor$$
• Trailing zeros of a general product: the scarcer prime wins · Zeros of a general product
  $$n=\min\big(v_2(P),\,v_5(P)\big)$$

Watch out for (7)

• Evaluate the expression before you factorise it
  → Canonical prime-power form
• Read whether 1 and N are to be excluded
  → Counting the divisors of a number
• The divisor sum is a product of sums, not a sum of products
  → Summing the divisors of a number
• Working backwards from a divisor count usually leaves several shapes
  → Odd divisors, divisors of a square, and working backwards
• Counting only the multiples of 5 undercounts
  → Counting the zeros at the end of a factorial
• Outside a factorial, do not assume the fives are the scarce prime
  → Trailing zeros of a general product: the scarcer prime wins
• Check the parity of a SUM before counting any factors
  → Trailing zeros of a general product: the scarcer prime wins

Formulas (7)

• HCF and LCM from the prime factorisations · HCF and LCM by exponents
  $$\mathrm{HCF}=\prod p_i^{\min(a_i,b_i)}, \qquad \mathrm{LCM}=\prod p_i^{\max(a_i,b_i)}$$
• The product law for two numbers · Product law (two numbers)
  $$\mathrm{HCF}(a,b)\cdot\mathrm{LCM}(a,b)=ab$$
• Writing the pair as H times coprime parts · The Ha, Hb substitution
  $$x=Ha,\; y=Hb,\; \gcd(a,b)=1 \;\Longrightarrow\; \frac{\mathrm{LCM}}{\mathrm{HCF}}=ab$$
• The subtraction property and its consequences · Subtraction property
  $$\mathrm{HCF}(n,\;n+k)=\mathrm{HCF}(n,\;k)$$
• HCF and LCM of fractions and decimals · Fractions: the crossed recipes
  $$\mathrm{LCM}\!\left(\frac{a_i}{b_i}\right)=\frac{\mathrm{LCM}(a_i)}{\mathrm{HCF}(b_i)}$$
• The HCF of two numbers of the form a to the n, minus one · HCF of power-minus-one
  $$\gcd\!\left(a^{m}-1,\;a^{n}-1\right)=a^{\gcd(m,n)}-1$$
• Spotting HCF and LCM data that cannot exist · The ratio test
  $$\frac{\mathrm{LCM}}{\mathrm{HCF}} = ab \in \mathbb{Z}^{+}$$

Watch out for (7)

• An LCM that is not a multiple of the HCF is impossible
  → HCF and LCM from the prime factorisations
• The product law is a TWO-number law
  → The product law for two numbers
• List only the COPRIME factor pairs, and expect more than one to survive
  → Writing the pair as H times coprime parts
• The property transfers the HCF, it does not compute it
  → The subtraction property and its consequences
• The two fraction recipes are crossed — do not use the same one twice
  → HCF and LCM of fractions and decimals
• Pull out the common constant before applying the identity
  → The HCF of two numbers of the form a to the n, minus one
• Some CDS questions carry data that cannot exist, and that is deliberate
  → Spotting HCF and LCM data that cannot exist

Formulas (7)

• When the answer is the HCF: the largest common measure · Tile count from the HCF
  $$\text{tiles}=\frac{L}{\mathrm{HCF}}\times\frac{W}{\mathrm{HCF}}$$
• When the answer is the LCM: things coinciding again · Coincidences within a window
  $$\text{count}=\left\lfloor \frac{\text{window}}{\mathrm{LCM}}\right\rfloor$$
• Largest, smallest and how many multiples in a range · Multiples in a range
  $$\#\{\text{multiples of } L \le N\}=\left\lfloor \frac{N}{L}\right\rfloor$$
• Recipe 1: same unknown remainder means take the HCF of the differences · Same-remainder recipe
  $$N_{\max}=\mathrm{HCF}\big(b-a,\;c-b\big)$$
• Recipe 2: the same remainder from every divisor means LCM times k, plus r · Common-remainder recipe
  $$N = L\,k + r, \qquad L=\mathrm{LCM}(d_1,\dots,d_k)$$
• Recipe 3: a constant shortfall means LCM times k, minus d · Constant-shortfall recipe
  $$N = L\,k - d, \qquad d = d_i - r_i \ \text{(the same for every } i)$$
• Layering an extra condition on a remainder recipe · Layered condition
  $$m \mid (Lk+r) \;\Longrightarrow\; Lk \equiv -r \pmod m$$

Watch out for (7)

• Largest tile and minimum number of tiles are the same question
  → When the answer is the HCF: the largest common measure
• How many MORE times excludes the start
  → When the answer is the LCM: things coinciding again
• An LCM multiple need not be a perfect square
  → Largest, smallest and how many multiples in a range
• Unknown remainder means differences; known remainder means subtract it
  → Recipe 1: same unknown remainder means take the HCF of the differences
• The stated remainder must be smaller than every divisor
  → Recipe 2: the same remainder from every divisor means LCM times k, plus r
• Check the shortfall is really constant before reaching for this
  → Recipe 3: a constant shortfall means LCM times k, minus d
• Do not stop at the family — the extra condition is the question
  → Layering an extra condition on a remainder recipe

Formulas (6)

• Replacing a number by its remainder · Reduce the base first
  $$a \equiv r \pmod n \;\Longrightarrow\; a^{k} \equiv r^{k} \pmod n$$
• When the base is one less than the modulus · Alternating powers
  $$a\equiv -1 \pmod n \;\Longrightarrow\; a^{k}\equiv(-1)^{k}\pmod n$$
• Finding the cycle of powers modulo n · Cycle reduction
  $$a^{t}\equiv 1 \pmod n \;\Longrightarrow\; a^{k}\equiv a^{\,k \bmod t} \pmod n$$
• Fermat's little theorem · Fermat's little theorem
  $$a^{p-1}\equiv 1 \pmod p \quad (p \text{ prime},\ p \nmid a)$$
• Pairing terms that cancel modulo n · Cancelling pair
  $$a+b\equiv 0 \pmod n,\ k \text{ odd} \;\Longrightarrow\; a^{k}+b^{k}\equiv 0$$
• Remainders of sums, differences and products of given remainders · Combining remainders
  $$m\equiv r_1,\ n\equiv r_2 \pmod d \;\Longrightarrow\; m\pm n\equiv r_1\pm r_2,\ \ mn\equiv r_1r_2$$

Watch out for (6)

• A remainder must land in 0 to n minus 1
  → Replacing a number by its remainder
• Odd power of minus one is the modulus minus one, not minus one
  → When the base is one less than the modulus
• Reduce the exponent modulo the CYCLE, not modulo the divisor
  → Finding the cycle of powers modulo n
• The exponent p minus one gives 1; the exponent p gives the base back
  → Fermat's little theorem
• Pair the bases before reducing them individually
  → Pairing terms that cancel modulo n
• m greater than n does not mean its remainder is greater
  → Remainders of sums, differences and products of given remainders

Formulas (6)

• Pulling the smallest power out of a sum of like powers · Power-sum extraction
  $$a^{m}+a^{m+1}+\cdots+a^{m+k}=a^{m}\!\left(1+a+\cdots+a^{k}\right)$$
• The a-to-the-n minus b-to-the-n identity · Difference of like powers
  $$a^{n}-b^{n}=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}\right)$$
• The a-to-the-n plus b-to-the-n identity · Sum of like powers, odd exponent
  $$a^{n}+b^{n}=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots+b^{n-1}\right) \quad (n \text{ odd})$$
• Rewriting mixed bases as powers of one number · Rebasing
  $$\left(a^{j}\right)^{k}=a^{jk}$$
• The largest number that ALWAYS divides an expression · The cap from the smallest case
  $$d \mid f(n)\ \forall n \;\Longrightarrow\; d \mid f(n_{\min})$$
• When a variable divides a polynomial in itself · Constant-term criterion
  $$x \mid \left(a_kx^{k}+\cdots+a_1x+c\right) \iff x \mid c$$

Watch out for (6)

• A new prime can only come from the bracket
  → Pulling the smallest power out of a sum of like powers
• a plus b needs an EVEN exponent for a difference
  → The a-to-the-n minus b-to-the-n identity
• The parity conditions for a sum and a difference are opposite
  → The a-to-the-n plus b-to-the-n identity
• Rebase before you sort, and sort before you factor
  → Rewriting mixed bases as powers of one number
• Whole numbers include zero, and that can break the statement
  → The largest number that ALWAYS divides an expression
• Count the divisors of the constant, not the values you happen to test
  → When a variable divides a polynomial in itself

Formulas (5)

• The nearest perfect square above or below · Distance to the neighbouring squares
  $$k^{2}\le N<(k+1)^{2}: \quad \text{subtract } N-k^{2}, \quad \text{add } (k+1)^{2}-N$$
• Difference of squares and the parity constraint on factor pairs · Difference of squares
  $$m^{2}-n^{2}=(m-n)(m+n)$$
• Completing the square to force a factorisation · Reduce to a constant difference of squares
  $$n^{2}+bn+c=k^{2} \;\Longrightarrow\; (2k)^{2}-(2n+b)^{2}=4c-b^{2}$$
• Expressions that are always perfect squares · Four consecutive integers plus one
  $$n(n+1)(n+2)(n+3)+1=\left(n^{2}+3n+1\right)^{2}$$
• Cubes, fourth powers and taxicab numbers · Taxicab identity
  $$1729 = 1^{3}+12^{3} = 9^{3}+10^{3}$$

Reference tables (1)

Watch out for (7)

• The last-digit test only rules out, never rules in
  → The last digit of a perfect square
• The number itself may not be a square even when it looks round
  → The nearest perfect square above or below
• Mixed-parity factor pairs must be discarded
  → Difference of squares and the parity constraint on factor pairs
• A prime target forces a unique pair
  → Difference of squares and the parity constraint on factor pairs
• An odd middle coefficient needs the factor of 4
  → Completing the square to force a factorisation
• Pair the OUTER factors, not adjacent ones
  → Expressions that are always perfect squares
• m to the n has a trivial solution that the question does not intend
  → Cubes, fourth powers and taxicab numbers

Formulas (2)

• Converting a recurring decimal to a fraction · Purely recurring decimal
  $$0.\overline{d_1d_2\cdots d_k}=\frac{d_1d_2\cdots d_k}{\underbrace{99\cdots9}_{k}}$$
• Deciding irrationality of roots, sums and products · Root test
  $$\sqrt{n} \in \mathbb{Q} \iff n \text{ is a perfect square}$$

Reference tables (1)

Watch out for (4)

• A square root is not automatically irrational
  → What makes a number rational, and what the decimal expansion reveals
• A pattern is not the same as a recurring block
  → What makes a number rational, and what the decimal expansion reveals
• The recurring bar changes the value, and the question turns on it
  → Converting a recurring decimal to a fraction
• Simplify the surd before judging it
  → Deciding irrationality of roots, sums and products