Number System and Divisibility

Remainders of powers

Remainders of powers are found with congruences. We write a \equiv b \pmod{m} when m divides a-b, which means a and b leave the same remainder on division by m. Congruences can be multiplied, so a \equiv b \pmod{m} implies a^{k} \equiv b^{k} \pmod{m} for every natural number k.

The method has two steps. First, reduce the base modulo m. A negative representative is often the simplest choice. For instance, 38 \equiv -1 \pmod{13}, so 38^{51} \equiv (-1)^{51} = -1 \equiv 12 \pmod{13}, because an odd power of -1 equals -1.

Second, find the cycle of powers. The residues of b^{k} modulo m repeat with some period, so the exponent may be reduced modulo that period. Powers of 2 modulo 7 read 2, 4, 1 and then repeat with period 3, so 2^{n} depends only on n \bmod 3. The remainder of a number modulo 3 equals the remainder of its digit sum modulo 3, which lets a long exponent be reduced quickly. For example, the powers of 3 modulo 7 repeat with period 6, and 100 \equiv 4 \pmod{6}, so 3^{100} \equiv 3^{4} = 81 \equiv 4 \pmod{7}.

When a base is congruent to 1, every power is 1. Since 28 \equiv 1 \pmod{9}, we get 28^{k} \equiv 1 \pmod{9} for every k, so the remainder is always 1.

Idempotent residues handle differences. Since 3^{k} \equiv 3 \pmod{6} for every k \ge 1, both 9^{k} and 21^{k} leave remainder 3 on division by 6, so 9^{k}-21^{k} is divisible by 6.

For the last digits, the last j digits of a number are its residue modulo 10^{j}. Since 25^{2}=625 and 625 \cdot 25 = 15625 also ends in 625, every power 25^{n} with n \ge 2 ends in 625. Hence its hundreds digit is 6.

When several powers are added, list the possible residues of each term modulo 10 and combine them. The number of distinct remainders is the number of residues the total can take. For a sum such as 4^{n}+9^{n}, the units digit of each term depends only on whether n is odd or even, because 4^{n} alternates between 4 and 6 and 9^{n} alternates between 9 and 1. Checking the two parity cases therefore gives all possible remainders over all n.

If the modulus is p+1, then p \equiv -1 \pmod{p+1}, so p^{n} \equiv (-1)^{n} \pmod{p+1}. The remainder depends only on the parity of n. Knowing that n is even already fixes the remainder, while knowing only p says nothing about n.

An odd-power sum can also vanish modulo m. If a \equiv -1 and b \equiv 1 \pmod{m}, then a^{n}+b^{n} \equiv (-1)^{n}+1, which is 0 for odd n. So the sum is divisible by m.

Problems with an unknown parameter reduce to linear congruences. Compute each expression modulo the given number, write the condition as a congruence on the parameter, and then take the least admissible value.

For squares modulo 5, the residues are 0, 1, 4. If 5 divides none of n-1, n, n+1, then n \equiv 2 or 3 \pmod{5}, and in both cases n^{2} \equiv 4 \equiv -1 \pmod{5}, so 5 \mid n^{2}+1.

Every odd n satisfies n^{2} \equiv 1 \pmod{8}, because n^{2}-1=(n-1)(n+1) is a product of two consecutive even numbers, which is divisible by 8. Hence every even power n^{2k}=(n^{2})^{k} leaves remainder 1 modulo 8. For example, 7^{4}=2401=300 \cdot 8+1.

The sum of cubes of three consecutive integers is divisible by 9, since n^{3}+(n+1)^{3}+(n+2)^{3}=3m(m^{2}+2) with m=n+1. If 3 \nmid m, then m^{2} \equiv 1 \pmod{3}, so m^{2}+2 is divisible by 3.

LCM and HCF applications

LCM and HCF problems rest on two facts. A common multiple is a multiple of the LCM, and a common divisor divides the HCF. Periodic events such as runners on a track or bells ringing at intervals coincide at multiples of the LCM of their periods. Equal square tiles and equal divisions of lengths are governed by the HCF.

For LCM, use prime factorisation and take the highest power of each prime. Periods of 8, 12 and 18 minutes give 2^{3} \cdot 3^{2} = 72 minutes as the LCM, so the events next coincide after 72 minutes.

If bells ring together at intervals whose LCM is 30 minutes, they ring together at 30, 60 and 90 minutes after a joint start. So in the 100 minutes that follow, there are 3 further joint rings.

If the LCM L and HCF H of two numbers are known, then L+H and L-H determine both. The product of the two numbers equals L \times H, so once the product and one number are known, the other follows. Note that the HCF must divide each number, so a computed value that the HCF does not divide signals inconsistent data.

Because the product of two numbers equals L \times H, the product is fixed once L and H are known. For a ratio L:H = 3:2, write L=3k and H=2k. Before using the ratio, check that H divides L, since otherwise the data cannot hold together.

If the HCF is h and the LCM is L, the two numbers are hx and hy with \gcd(x,y)=1 and L=hxy. Different coprime splittings of L/h give different pairs. For example, HCF 2 and LCM 30 give xy=15 with coprime splits (1,15) and (3,5), so the pairs (2,30) and (6,10) both qualify, with differences 28 and 4. The difference is therefore not always determined.

For fractions, the HCF equals the HCF of the numerators divided by the LCM of the denominators, and the LCM equals the LCM of the numerators divided by the HCF of the denominators. For \frac{4}{3} and \frac{6}{5}, the HCF is \frac{\text{HCF}(4,6)}{\text{LCM}(3,5)} = \frac{2}{15} and the LCM is \frac{\text{LCM}(4,6)}{\text{HCF}(3,5)} = 12.

A number that leaves remainder r on division by several numbers has the form r+kL, where L is the LCM of those numbers. For remainder 5 on division by 6 and by 8, the numbers are 5+24k. The largest such number below 1000 is 5 + 24 \cdot 41 = 989, since adding another 24 exceeds 1000.

Equal square tiles covering a rectangle have the largest possible side equal to the HCF of the two dimensions, expressed in the same unit. A 4 m by 6 m room gives tiles of side 200 cm, so 2 \times 3 = 6 tiles are needed.

By prime factorisation, the HCF takes the minimum power of each common prime. For example, 72 = 2^{3} \cdot 3^{2} and 90 = 2 \cdot 3^{2} \cdot 5 give \text{HCF} = 2 \cdot 3^{2} = 18. When one number contains variables, compare the prime powers on both sides, keeping in mind that the intended reading of such a condition must be checked.

Two numbers are coprime when their HCF is 1. If d divides both 12n+2 and 8n+1, then d divides 2(8n+1)-(12n+2)=4n. Since 8n+1 is odd and coprime to n, the HCF is 1 for every n, so the pair is coprime for each natural n.

A number leaving the same remainder r on division by several numbers is r plus a multiple of their LCM. For example, N = 360k + 2 leaves remainder 2 when divided by 4, 6, 8, 9 and 10. The first such terms are 362, 722 and 1082.

A given LCM together with one number does not always determine the other number. If \operatorname{LCM}(12,b)=60, then b may be 5, 10 or 20, so the sum 12+b is not fixed. For the question to be answerable, the data must determine the unknown uniquely.

Divisibility of exponential sums

Exponential sums are divisible by sums or differences of their bases through factor identities. The standard rules are as follows. For every natural n, x-y divides x^{n}-y^{n}. For odd n, x+y divides x^{n}+y^{n}. For even n, x+y divides x^{n}-y^{n}, because x^{2}-y^{2}=(x-y)(x+y) is a factor.

For odd n, a^{n}+b^{n} is divisible by a+b. For example, 2^{3}+1^{3}=9 is divisible by 2+1=3, and 3^{5}+2^{5}=275 is divisible by 3+2=5.

A sum of the form x^{n}+y^{n} is divisible by x+y only when n is odd. Substituting x=-y gives (-y)^{n}+y^{n}, which is 0 exactly when n is odd. For even n, the value becomes 2y^{n} \neq 0, so x+y is not a factor. Thus knowing that n is even answers the question, while knowing only that n is natural does not.

To expose the factors, write both terms in a common base and factor out the lower power. Since 27^{5} = 3^{15}, we get 3^{15} + 3^{13} = 3^{13}(3^{2}+1) = 3^{13} \cdot 10. Similarly, 2^{7}+2^{4} = 2^{4}(2^{3}+1) = 2^{4} \cdot 9.

A sum of consecutive powers r^{k}+r^{k+1}+\cdots+r^{k+j} equals r^{k}\cdot\dfrac{r^{j+1}-1}{r-1}, so the bracket is the factor to examine. For four terms, 1+r+r^{2}+r^{3} = (1+r)(1+r^{2}). With r=4, this gives 85 = 5 \cdot 17. For example, 2^{2}+2^{3}+2^{4}+2^{5} = 4(1+2+4+8) = 60 is divisible by 5 and 3.

For even n, x^{n}-y^{n} is divisible by x+y. For example, 8^{4}-5^{4} = 3471 = 13 \cdot 267 is divisible by 8+5=13. A number of the form x^{n}-y^{n} is therefore divisible by both x-y and, when n is even, x+y.

To test divisibility of a sum of powers by a prime p, reduce each base modulo p. If both bases are multiples of p, every term is divisible by p. For example, 15 and 6 are both multiples of 3, so 15^{n}+6^{m} is divisible by 3 for n, m \ge 1. Since 555 = 5 \cdot 111 = 5 \cdot 3 \cdot 37 and 777 = 7 \cdot 111, sums of powers of these bases are divisible by 37 and 3.

The expression \dfrac{3m^{3}+2m^{2}+5m+n}{m} = 3m^{2}+2m+5+\dfrac{n}{m} is an integer exactly when m divides n. So if it is not an integer, then n is not divisible by m. Also, 5(8^{m})+2^{3m} = 6 \cdot 8^{m}, and at m=0, which is a whole number, this equals 6. It is therefore not divisible by 48 for every whole number m.

Prime numbers

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself. A natural number greater than 1 that is not prime is called composite. The number 1 is neither prime nor composite, and 2 is the only even prime. Do not confuse prime with odd: 9 is odd but composite, and 2 is prime but even. To test whether n is prime, check that no prime p\le\sqrt{n} divides it, because every composite n has a prime factor not exceeding \sqrt{n}. For example, 91=7\times13 is composite, while 101 has no prime factor up to \sqrt{101}\approx10, so it is prime. A number is shown to be composite by exhibiting any factorisation into two factors greater than 1.

If p and q are distinct primes, they share no common factor, so \text{lcm}(p,q)=pq. Hence the two primes are found by factorising a given lcm, and their difference follows directly. For instance, \text{lcm}=3\times11=33 gives the primes 3 and 11.

When a difference condition such as m-n=k is imposed on primes within a range, the reliable method is to list all primes in that range and test each candidate pair. This systematic listing is the usual way to count such pairs in an examination.

The sum of two odd primes is even and greater than 2, so it can never be prime. Therefore, if x, y, x+y and x-y are all prime, one of x and y must equal 2, which narrows the search sharply.

• prime — exactly two positive divisors, e.g. 13 has only the divisors 1 and 13.
• composite — has a divisor other than 1 and itself, e.g. 15=3\times5.
• lcm of distinct primes — equals their product, e.g. \text{lcm}(5,7)=35.

Properties of negative real numbers

If x is a negative real number, then every positive multiple of x is negative, so kx<0 for every natural number k, and no natural multiple of x can be positive. Multiplying by a negative number reverses an inequality. For x<0 we have 2x<x and x<-x, so the chain 2x<x<-x holds.

The square of a negative number is positive, but adding x can change the sign. The expression x^2+x=x(x+1) is negative when -1<x<0; for example, x=-\tfrac13 gives x^2+x=-\tfrac29.

The square of a negative real number is not necessarily rational. For x=-\pi, x^2=\pi^2 is irrational.

An odd power has the same sign as its base, so y^3=3x forces y and x to share a sign. An even power is non-negative and positive whenever its base is nonzero, so x^8y^9<0 forces y<0, while x^9y^{10}<0 forces x<0.

In data sufficiency questions, a statement is sufficient only if it alone, or together with the other statement, fixes a single answer to the question. A statement that fixes only the sign of one variable is insufficient when the question depends on both. Two statements that each fix one sign can together settle the sign of a product.

Knowing that \frac{m}{n}>1 does not decide whether m>n. The ratio means m and n have the same sign and |m|>|n|; if n>0 then m>n, but if n<0 then m<n. The condition m>2n alone also leaves the sign of n open. Together these two conditions still allow both cases, so the order cannot be determined.

• sufficient — the statement(s) determine a unique answer to the question.
• insufficient — admissible values exist that give both a yes and a no answer.
• odd power — keeps the sign, e.g. (-2)^3=-8.

Divisibility rules

A number is divisible by 9 exactly when its digit sum is divisible by 9. This test is the standard tool for finding a missing digit. For example, 4815 has digit sum 18, so it is divisible by 9.

A number is divisible by 25 when its last two digits are 00, 25, 50 or 75. For a number whose units digit is 5, the tens digit must therefore be 2 or 7, so only two candidate values arise for a missing tens digit.

Since 10^6\equiv1\pmod{13}, the place values repeat modulo 13 with period 6: 10^0,10^1,\dots,10^5\equiv1,10,9,12,3,4\pmod{13}. Multiplying each digit by the residue of its place value and adding gives a number congruent to the original modulo 13. The whole number is divisible by 13 exactly when this weighted sum is.

For a missing digit in a longer number, first compute the weighted sum of the known digits, then find the digit that makes the total a multiple of 13.

Since 100-1=99, the difference between a three-digit number \overline{abc} and its reversal is \overline{abc}-\overline{cba}=99(a-c). Any such difference is therefore an exact multiple of 99, and its remainder on division by 99 is 0.

• divisible by 3 — digit sum divisible by 3, e.g. 1P2 is divisible by 3 when 3+P is a multiple of 3.
• divisible by 4 — last two digits divisible by 4, e.g. 3412 is divisible by 4 because 12 is.

Unit digits of powers

The unit digit of a^n depends only on the unit digit of a and on the exponent n. The unit digits of successive powers repeat in cycles: for base 2 they are 2, 4, 8, 6; for base 3 they are 3, 9, 7, 1; for base 7 they are 7, 9, 3, 1. Bases ending in 4 or 9 have period 2, giving 4, 6 and 9, 1. Bases ending in 0, 1, 5 or 6 keep the same unit digit.

For a cycle of length 4, reduce the exponent modulo 4 and read the unit digit at that position, with remainder 0 corresponding to the fourth term of the cycle. For example, the unit digit of 3^{50} is 9, because 50\equiv2\pmod4 and the second term of the cycle 3, 9, 7, 1 is 9.

The unit digit of a sum or product depends only on the unit digits of the terms. So the unit digit of u+v is the unit digit of the sum of the unit digits of u and v, and this rule is used to combine two powers in one expression.

A digit D coprime to 10 satisfies D^4\equiv1\pmod{10}. Hence, when the exponent is a multiple of 4, D^{100} ends in 1 for D=1,3,7,9. The other digits give an even digit, 5 or 0 when raised to a power, so they never end in 1.

• cycle length — the period of unit digits: 4 for bases ending in 2, 3, 7 or 8; 2 for bases ending in 4 or 9; 1 for bases ending in 0, 1, 5 or 6.
• unit digit of 7^8 — is 1, since 8\equiv0\pmod4.

Consecutive integer sequences

A sequence of k consecutive integers has the form n,n+1,\dots,n+k-1. The product of any k consecutive integers is divisible by k!. In particular, the product of three consecutive integers is divisible by 3!=6.

Consecutive odd integers differ by 2. If y=x+2, then x+y=2x+2, which is always even.

If a sequence of consecutive integers contains 0, its product is 0, so the product equals one of the members. For a sequence of length at least 2 that contains no zero, all members have the same sign. The absolute value of the product then exceeds the absolute value of every member, so the product can never equal a member.

Even powers hide the sign: t^4=256 allows both t=4 and t=-4, so such a condition fixes only |t|. Combining it with an inequality that bounds t from above, for example t<\sqrt[3]{16}, can leave a single value.

• consecutive integers — differ by 1 at each step, e.g. -2,-1,0,1,2.
• consecutive odd integers — differ by 2, e.g. -3,-1,1; their sum is always even.

Continued fraction representation

A finite simple continued fraction has the form a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cdots}}, where a_0 is an integer and a_1,a_2,\dots are positive integers. It is written [a_0;a_1,a_2,\dots], and the a_i are called partial quotients. Every rational number has such an expansion. The expansion is unique when its last partial quotient is greater than 1.