Elementary Number Theory and Combinatorics Questions and Answers

Q: Which of the following natural numbers cannot be written as a sum of 2 squares ?

The number that is not a sum of two squares is 1111.A number is a sum of two squares exactly when every prime \(\equiv 3 \pmod 4\) in its factorisation appears to an even power. \(1111 = 11 \times 101\), and 11 \(\equiv 3 \pmod 4\) appears once. A quicker check: \(1111 \equiv 3 \pmod 4\), and a sum of two squares is 0, 1 or 2 mod 4.The others are sums of two squares: \(405 = 18^{2} + 9^{2}\), \(117 = 9^{2} + 6^{2}\), and \(164 = 10^{2} + 8^{2}\).

Q: The linear diophantine equation \(7x - 8y = 5\) has :

The equation has infinitely many integer solutions, with any two values of \(x\) differing by a multiple of 8.\(\gcd(7, 8) = 1\) divides 5, so solutions exist. One solution is \(x = 3, y = 2\), since \(21 - 16 = 5\). The general solution is\[ x = 3 + 8t, \quad y = 2 + 7t, \quad t \in \mathbf{Z} \]So there are infinitely many solutions, and the \(x\)-values differ by multiples of 8 (the coefficient of \(y\) divided by the gcd). It is the \(y\)-values that differ by multiples of 7, which is the trap in option D.

Q: Which of the following is a quadratic residue modulo 43 ?

The quadratic residue is 40.\(40 \equiv -3 \pmod{43}\). Using Legendre symbols, with \(43 \equiv 3 \pmod 4\):\[ \begin{aligned} \left(\tfrac{-1}{43}\right) &= -1 \\ \left(\tfrac{3}{43}\right) &= -\left(\tfrac{43}{3}\right) = -\left(\tfrac{1}{3}\right) = -1 \\ \left(\tfrac{-3}{43}\right) &= (-1)(-1) = 1 \end{aligned} \]So 40 is a residue. (Indeed \(13^{2} = 169 = 3 \cdot 43 + 40\).) The others are not: -1 and 3 have symbol -1 as computed, and since \(43 \equiv 3 \pmod 8\), \((2/43) = -1\).

Q: If \(\mu\) is the Mobius function and \(n\) is a positive integer, then \(\mu(n)\ \mu(n + 1)\ \mu(n + 2)\ \mu(n + 3)\) is equal to :

The product is 0.Among any four consecutive integers \(n, n + 1, n + 2, n + 3\), one is divisible by 4. That number has the square factor \(2^{2}\), so the Mobius function is 0 there, and the whole product is 0.The Mobius function only takes the values 0, 1 and -1, so a product of four values can never be 4 or 6. A value of 1 would need all four numbers to be square-free, which the divisibility by 4 rules out.

Q: The coefficient of \(x^{8}\) in \((x^{2} + x^{3} + x^{4} + x^{5})^{5}\) is :

The coefficient is 0.Every term of \((x^{2} + x^{3} + x^{4} + x^{5})^{5}\) is a product of five factors, each of degree at least 2, so every term has degree at least \(5 \times 2 = 10\). In fact\[ \begin{aligned} (x^{2} + \cdots + x^{5})^{5} \\ = x^{10}(1 + x + x^{2} + x^{3})^{5} \end{aligned} \]so the lowest power present is \(x^{10}\), and \(x^{8}\) does not occur.13, 10 and 20 would be coefficients of higher powers; for example the coefficient of \(x^{11}\) is 5. The trap is to count solutions of \(e_{1} + \cdots + e_{5} = 8\) without noticing each \(e_{i} \ge 2\).

Q: Every natural number is :

Every natural number is a sum of distinct powers of 2.This is the binary representation: every natural number \(n\) can be written uniquely as \(\sum b_{k}2^{k}\) with each \(b_{k} \in \{0, 1\}\), i.e. as a sum of distinct powers of 2. For example \(13 = 8 + 4 + 1\).The others fail. 2 is not a sum of distinct powers of 3 (only 1, 3, 9, ... are available). 5 is not a sum of distinct factorials (1, 2, 6, ...): 1 + 2 = 3 and the next is 6. And 2 is not a sum of distinct triangular numbers (1, 3, 6, ...).

Q: Which of the following is a solution to the system of congruences :\(x \equiv 2 \pmod{5}\)\(x \equiv 3 \pmod{4}\)\(x \equiv 1 \pmod{3}\)

The solution is 67.Check each candidate against the three congruences:xmod 5mod 4mod 322221272304723267231Only 67 gives remainders 2, 3 and 1. By the Chinese remainder theorem the solutions are exactly \(x \equiv 67 \pmod{60}\). 22 fails mod 4, 27 fails mod 3 and 47 fails mod 3.

Q: Modulo the prime 101, the number \((50\,!)^{2}\) is congruent to :

\((50!)^{2} \equiv\) -1 (mod 101).By Wilson's theorem, \(100! \equiv -1 \pmod{101}\). Pair each factor \(k \le 50\) with \(101 - k \equiv -k\):\[ \begin{aligned} 100! &= \prod_{k=1}^{50} k(101 - k) \\ &\equiv \prod_{k=1}^{50} (-k^{2}) = (-1)^{50}(50!)^{2} \end{aligned} \]Since \((-1)^{50} = 1\), \((50!)^{2} \equiv 100! \equiv -1\). This also shows that -1 is a square mod 101, as it must be because \(101 \equiv 1 \pmod{4}\).The value cannot be 0, since 101 is prime and does not divide 50!, and 1 and 2 do not satisfy Wilson's theorem here.

Q: How many distinct terms are there in the expansion of \((w + x + y + z)^{10}\) ?

There are 286 distinct terms.The terms of the expansion are the monomials \(w^{a} x^{b} y^{c} z^{d}\) with \(a + b + c + d = 10\) and each exponent a non-negative integer. Counting such solutions is the stars-and-bars problem: 10 stars and 3 bars in a row.\[ \begin{aligned} \binom{10 + 4 - 1}{4 - 1} &= \binom{13}{3} \\ &= \frac{13 \times 12 \times 11}{6} = 286 \end{aligned} \]Each such monomial appears with a positive multinomial coefficient, so none cancels. The figures 224, 228 and 281 do not come from the correct count; a common slip is \(\binom{12}{3} = 220\), which uses \(n + k - 2\) instead of \(n + k - 1\).

Q: What is the last digit in \(3^{55}\) ?

The last digit of \(3^{55}\) is 7.Last digits of powers of 3 repeat with period 4:\[ \begin{aligned} &3^{1} = 3,\ 3^{2} = 9,\ 3^{3} = 27, \\ &3^{4} = 81,\ 3^{5} = 243, \ldots \end{aligned} \]so the cycle of last digits is 3, 9, 7, 1. Since \(55 = 4 \times 13 + 3\), \(3^{55}\) has the same last digit as \(3^{3}\), which is 7. In congruence form, \(3^{4} \equiv 1 \pmod{10}\), so \(3^{55} = (3^{4})^{13} \cdot 3^{3} \equiv 27 \equiv 7\).The digit 1 would need an exponent divisible by 4 and 3 an exponent of the form \(4k + 1\). The digit 5 never occurs, because no power of 3 is divisible by 5.

11.

Which of the following natural numbers cannot be written as a sum of 2 squares ?

A.405
B.1111
C.117
D.164

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: B

The number that is not a sum of two squares is 1111.

A number is a sum of two squares exactly when every prime \(\equiv 3 \pmod 4\) in its factorisation appears to an even power. \(1111 = 11 \times 101\), and 11 \(\equiv 3 \pmod 4\) appears once. A quicker check: \(1111 \equiv 3 \pmod 4\), and a sum of two squares is 0, 1 or 2 mod 4.

The others are sums of two squares: \(405 = 18^{2} + 9^{2}\), \(117 = 9^{2} + 6^{2}\), and \(164 = 10^{2} + 8^{2}\).

Discuss in Forum

12.

The linear diophantine equation \(7x - 8y = 5\) has :

A.exactly one integer solution
B.exactly two integer solutions
C.infinitely many integer solutions and the difference between any two values of \(x\) in the solutions is divisible by 8.
D.infinitely many integer solutions and the difference between any two values of \(x\) in the solutions is divisible by 7

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

The equation has infinitely many integer solutions, with any two values of \(x\) differing by a multiple of 8.

\(\gcd(7, 8) = 1\) divides 5, so solutions exist. One solution is \(x = 3, y = 2\), since \(21 - 16 = 5\). The general solution is

\[ x = 3 + 8t, \quad y = 2 + 7t, \quad t \in \mathbf{Z} \]

So there are infinitely many solutions, and the \(x\)-values differ by multiples of 8 (the coefficient of \(y\) divided by the gcd). It is the \(y\)-values that differ by multiples of 7, which is the trap in option D.

Discuss in Forum

13.

Which of the following is a quadratic residue modulo 43 ?

A.-1
B.40
C.2
D.3

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: B

The quadratic residue is 40.

\(40 \equiv -3 \pmod{43}\). Using Legendre symbols, with \(43 \equiv 3 \pmod 4\):

\[ \begin{aligned} \left(\tfrac{-1}{43}\right) &= -1 \\ \left(\tfrac{3}{43}\right) &= -\left(\tfrac{43}{3}\right) = -\left(\tfrac{1}{3}\right) = -1 \\ \left(\tfrac{-3}{43}\right) &= (-1)(-1) = 1 \end{aligned} \]

So 40 is a residue. (Indeed \(13^{2} = 169 = 3 \cdot 43 + 40\).) The others are not: -1 and 3 have symbol -1 as computed, and since \(43 \equiv 3 \pmod 8\), \((2/43) = -1\).

Discuss in Forum

14.

If \(\mu\) is the Mobius function and \(n\) is a positive integer, then \(\mu(n)\ \mu(n + 1)\ \mu(n + 2)\ \mu(n + 3)\) is equal to :

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: B

The product is 0.

Among any four consecutive integers \(n, n + 1, n + 2, n + 3\), one is divisible by 4. That number has the square factor \(2^{2}\), so the Mobius function is 0 there, and the whole product is 0.

The Mobius function only takes the values 0, 1 and -1, so a product of four values can never be 4 or 6. A value of 1 would need all four numbers to be square-free, which the divisibility by 4 rules out.

Discuss in Forum

15.

The coefficient of \(x^{8}\) in \((x^{2} + x^{3} + x^{4} + x^{5})^{5}\) is :

A.13
B.10
C.20
D.0

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: D

The coefficient is 0.

Every term of \((x^{2} + x^{3} + x^{4} + x^{5})^{5}\) is a product of five factors, each of degree at least 2, so every term has degree at least \(5 \times 2 = 10\). In fact

\[ \begin{aligned} (x^{2} + \cdots + x^{5})^{5} \\ = x^{10}(1 + x + x^{2} + x^{3})^{5} \end{aligned} \]

so the lowest power present is \(x^{10}\), and \(x^{8}\) does not occur.

13, 10 and 20 would be coefficients of higher powers; for example the coefficient of \(x^{11}\) is 5. The trap is to count solutions of \(e_{1} + \cdots + e_{5} = 8\) without noticing each \(e_{i} \ge 2\).

Discuss in Forum

16.

Every natural number is :

A.a sum of distinct powers of 2
B.a sum of distinct powers of 3
C.a sum of distinct factorials
D.a sum of distinct triangular numbers

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: A

Every natural number is a sum of distinct powers of 2.

This is the binary representation: every natural number \(n\) can be written uniquely as \(\sum b_{k}2^{k}\) with each \(b_{k} \in \{0, 1\}\), i.e. as a sum of distinct powers of 2. For example \(13 = 8 + 4 + 1\).

The others fail. 2 is not a sum of distinct powers of 3 (only 1, 3, 9, ... are available). 5 is not a sum of distinct factorials (1, 2, 6, ...): 1 + 2 = 3 and the next is 6. And 2 is not a sum of distinct triangular numbers (1, 3, 6, ...).

Discuss in Forum

17.

Which of the following is a solution to the system of congruences :

\(x \equiv 2 \pmod{5}\)
\(x \equiv 3 \pmod{4}\)
\(x \equiv 1 \pmod{3}\)

A.22
B.27
C.47
D.67

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: D

The solution is 67.

Check each candidate against the three congruences:

x	mod 5	mod 4	mod 3
22	2	2	1
27	2	3	0
47	2	3	2
67	2	3	1

Only 67 gives remainders 2, 3 and 1. By the Chinese remainder theorem the solutions are exactly \(x \equiv 67 \pmod{60}\). 22 fails mod 4, 27 fails mod 3 and 47 fails mod 3.

Discuss in Forum

18.

Modulo the prime 101, the number \((50\,!)^{2}\) is congruent to :

A.-1
B.1
C.0
D.2

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: A

\((50!)^{2} \equiv\) -1 (mod 101).

By Wilson's theorem, \(100! \equiv -1 \pmod{101}\). Pair each factor \(k \le 50\) with \(101 - k \equiv -k\):

\[ \begin{aligned} 100! &= \prod_{k=1}^{50} k(101 - k) \\ &\equiv \prod_{k=1}^{50} (-k^{2}) = (-1)^{50}(50!)^{2} \end{aligned} \]

Since \((-1)^{50} = 1\), \((50!)^{2} \equiv 100! \equiv -1\). This also shows that -1 is a square mod 101, as it must be because \(101 \equiv 1 \pmod{4}\).

The value cannot be 0, since 101 is prime and does not divide 50!, and 1 and 2 do not satisfy Wilson's theorem here.

Discuss in Forum

19.

How many distinct terms are there in the expansion of \((w + x + y + z)^{10}\) ?

A.228
B.224
C.281
D.286

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: D

There are 286 distinct terms.

The terms of the expansion are the monomials \(w^{a} x^{b} y^{c} z^{d}\) with \(a + b + c + d = 10\) and each exponent a non-negative integer. Counting such solutions is the stars-and-bars problem: 10 stars and 3 bars in a row.

\[ \begin{aligned} \binom{10 + 4 - 1}{4 - 1} &= \binom{13}{3} \\ &= \frac{13 \times 12 \times 11}{6} = 286 \end{aligned} \]

Each such monomial appears with a positive multinomial coefficient, so none cancels. The figures 224, 228 and 281 do not come from the correct count; a common slip is \(\binom{12}{3} = 220\), which uses \(n + k - 2\) instead of \(n + k - 1\).

Discuss in Forum

20.

What is the last digit in \(3^{55}\) ?

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: D

The last digit of \(3^{55}\) is 7.

Last digits of powers of 3 repeat with period 4:

\[ \begin{aligned} &3^{1} = 3,\ 3^{2} = 9,\ 3^{3} = 27, \\ &3^{4} = 81,\ 3^{5} = 243, \ldots \end{aligned} \]

so the cycle of last digits is 3, 9, 7, 1. Since \(55 = 4 \times 13 + 3\), \(3^{55}\) has the same last digit as \(3^{3}\), which is 7. In congruence form, \(3^{4} \equiv 1 \pmod{10}\), so \(3^{55} = (3^{4})^{13} \cdot 3^{3} \equiv 27 \equiv 7\).

The digit 1 would need an exponent divisible by 4 and 3 an exponent of the form \(4k + 1\). The digit 5 never occurs, because no power of 3 is divisible by 5.

Elementary Number Theory and Combinatorics Questions and Answers

Topics

Other Subjects

Tags: Elementary Number Theory and Combinatorics Questions and Answers

About Us

Elementary Number Theory and Combinatorics Questions and Answers

Topics

Other Subjects

Tags: Elementary Number Theory and Combinatorics Questions and Answers

About Us

Stay informed about all important Dates & Notifications