Elementary Number Theory and Combinatorics Questions and Answers

Answer: A

Only one statement is true: \(\sum_{k=0}^{6} (-1)^{k}\binom{13}{2k} = -64\). The final key accepts this option alone.

Expand \((1 + i)^{13} = \sum_{j} \binom{13}{j} i^{j}\). The even terms \(j = 2k\) give \(i^{2k} = (-1)^{k}\), the real part; the odd terms give \(i^{2k+1} = (-1)^{k}i\), the imaginary part. In polar form:

\[ \begin{aligned} 1 + i &= \sqrt{2}\,e^{i\pi/4} \\ (1 + i)^{13} &= 2^{13/2}\,e^{13i\pi/4} \\ &= 64\sqrt{2}\left(-\tfrac{1}{\sqrt{2}} - \tfrac{i}{\sqrt{2}}\right) \\ &= -64 - 64i \end{aligned} \]

since \(\frac{13\pi}{4} = 2\pi + \frac{5\pi}{4}\). So the even alternating sum is \(-64\), not 64, and the odd alternating sum is also \(-64\), which is neither 128 nor \(-128\).

Answer: B

The coefficient is 210.

By the multinomial theorem the coefficient of \(x^{a}y^{b}z^{c}\) in \((x + y + z)^{n}\), with \(a + b + c = n\), is \(\dfrac{n!}{a!\,b!\,c!}\). Here \(n = 7\), \(a = 2\), \(b = 2\), \(c = 3\):

\[ \begin{aligned} \frac{7!}{2!\,2!\,3!} &= \frac{5040}{2 \cdot 2 \cdot 6} \\ &= \frac{5040}{24} = 210 \end{aligned} \]

Counting another way: choose the 3 brackets that give \(z\) (\(\binom{7}{3} = 35\)), then 2 of the remaining 4 for \(x\) (\(\binom{4}{2} = 6\)): \(35 \times 6 = 210\). 420 and 630 are this times 2 and 3, from dividing by too few factorials.

Answer: D

The dual statement is \(((\sim p) \wedge q) \vee ((\sim p) \wedge r)\).

The dual is formed from an expression in \(\wedge\), \(\vee\) and \(\sim\) by swapping \(\wedge\) with \(\vee\). First remove the implication:

\[ p \Rightarrow q \wedge r \equiv (\sim p) \vee (q \wedge r) \]

Its dual is \((\sim p) \wedge (q \vee r)\), and distributing \(\sim p\) over the disjunction gives \(((\sim p) \wedge q) \vee ((\sim p) \wedge r)\), option D.

Option B is \((\sim p) \vee (q \vee r)\), which swaps only the inner connective. Option A leaves \(p\) unnegated, and option C negates the wrong letters.

Answer: D

The number is 6000.

Use inclusion-exclusion on 1 to 10,000. Multiples of 5, 6 and 8: \(\lfloor 10000/5 \rfloor = 2000\), \(\lfloor 10000/6 \rfloor = 1666\), \(\lfloor 10000/8 \rfloor = 1250\). Pairwise, with lcm(5, 6) = 30, lcm(5, 8) = 40 and lcm(6, 8) = 24: 333, 250 and 416. All three, lcm 120: 83.

\[ \begin{aligned} |A \cup B \cup C| &= 4916 - 999 + 83 \\ &= 4000 \end{aligned} \]

So \(10000 - 4000 = 6000\) are divisible by none of them. The trap is the pair 6 and 8, whose lcm is 24, not 48; using 48 changes the count.

Answer: A

\(a_{12} =\) 31250.

Put \(b_{n} = a_{n}^{2}\). The recurrence becomes \(b_{n+1} = 5b_{n}\) with \(b_{0} = 4\), so \(b_{n} = 4 \cdot 5^{n}\). Since \(a_{n} \gt 0\), \(a_{n} = 2 \cdot 5^{n/2}\). Then

\[ a_{12} = 2 \cdot 5^{6} = 2 \times 15625 = 31250 \]

The positivity condition is what fixes the sign of each square root; without it \(a_{12}\) could be \(\pm 31250\). The other options are near misses with no derivation behind them.

Answer: B

The number is 2015.

Legendre's three-square theorem: a natural number is a sum of three squares if and only if it is not of the form \(4^{a}(8b + 7)\). None of the options is divisible by 4, so check each modulo 8:

\[ \begin{aligned} 2013 &\equiv 5, \quad 2015 \equiv 7 \\ 2017 &\equiv 1, \quad 2019 \equiv 3 \pmod 8 \end{aligned} \]

Only 2015 is \(\equiv 7 \pmod 8\), so it alone cannot be written as a sum of three squares. (A square is 0, 1 or 4 mod 8, and no three of these add to 7.)

Answer: D

The congruence is solvable for \(p = 23\).

By the second supplement to quadratic reciprocity, 2 is a quadratic residue modulo an odd prime \(p\) exactly when \(p \equiv \pm 1 \pmod 8\). \(23 \equiv 7 \equiv -1 \pmod 8\), so 2 is a residue. Indeed \(5^{2} = 25 \equiv 2 \pmod{23}\).

The others are \(\equiv \pm 3 \pmod 8\): \(5 \equiv 5\), \(13 \equiv 5\) and \(19 \equiv 3\), so 2 is a non-residue and \(x^{2} \equiv 2\) has no solution for them.

Answer: A

The sum is 24.

Gauss's identity says \(\sum_{d|n}\varphi(d) = n\) for every \(n\). Checking with the divisors of 24:

\[ \begin{aligned} &\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) \\ &+ \varphi(6) + \varphi(8) + \varphi(12) + \varphi(24) \\ &= 1 + 1 + 2 + 2 + 2 + 4 + 4 + 8 = 24 \end{aligned} \]

The reason is that each of the numbers 1 to 24 has a unique gcd \(g\) with 24, and those with gcd \(g\) number \(\varphi(24/g)\). 25 and 23 are off by one, and 20 omits terms.

Answer: D

A square is of the form \(3k\) or \(3k - 2\).

Any integer is \(3m\), \(3m + 1\) or \(3m - 1\), and

\[ (3m)^{2} = 9m^{2},\quad (3m \pm 1)^{2} = 9m^{2} \pm 6m + 1 \]

So a square leaves remainder 0 or 1 on division by 3. Remainder 1 can be written \(3k - 2\) (with \(k = m' + 1\)), so squares are \(3k\) or \(3k - 2\).

The other options fail: \(3k - 1\) means remainder 2, impossible; \(4k - 1\) means remainder 3 mod 4, but squares are 0 or 1 mod 4; and \(5k\) or \(5k + 1\) misses squares like 4 and 9, which are 4 mod 5.

Answer: C

The last two digits are 27.

Work modulo 100. \(3^{10} = 59049 \equiv 49\), so \(3^{20} \equiv 49^{2} = 2401 \equiv 1\). Since \(123 = 6 \cdot 20 + 3\),

\[ 3^{123} = (3^{20})^{6} \cdot 3^{3} \equiv 1 \cdot 27 = 27 \]

The other endings belong to other exponents: \(3^{3} \equiv 27\), \(3^{7} \equiv 87\), \(3^{11} \equiv 47\), \(3^{19} \equiv 67\) (mod 100).