Number Theory Self Test

Number Theory Quiz

Test your knowledge of divisibility, prime numbers, modular arithmetic, and more

Q1

The division algorithm states that for any integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ and $r$ such that:

$a = bq + r$ where $0 \leq r < b$ $a = bq + r$ where $0 < r \leq b$ $a = bq + r$ where $0 \leq r \leq b$ $a = bq + r$ where $-b < r < b$

Q2

The Euclidean algorithm for finding $\gcd(a,b)$ is based on which property?

$\gcd(a,b) = \gcd(b, a \bmod b)$ $\gcd(a,b) = \gcd(a-b, b)$ $\gcd(a,b) = \gcd(a+b, b)$ $\gcd(a,b) = \gcd(a, b-a)$

Q3

For any positive integers $a$ and $b$, which of the following is true?

$\gcd(a,b) \cdot \text{lcm}(a,b) = ab$ $\gcd(a,b) + \text{lcm}(a,b) = a + b$ $\gcd(a,b) = \text{lcm}(a,b)$ if and only if $a = b$ $\gcd(a,b) \leq \text{lcm}(a,b)$

Q4

Which of the following is NOT true about prime numbers?

There are infinitely many prime numbers Every integer greater than 1 is either prime or can be written as a product of primes There exists a largest prime number 2 is the only even prime number

Q5

The fundamental theorem of arithmetic states that:

Every integer greater than 1 can be uniquely factored into prime numbers, up to the order of the factors Every integer greater than 1 can be factored into prime numbers Every prime number is odd except for 2 Every integer greater than 1 has at least one prime factor

Q6

Two integers $a$ and $b$ are congruent modulo $m$ (written $a \equiv b \pmod{m}$) if:

$m$ divides $a - b$ $a$ divides $b$ $b$ divides $a$ $m$ divides $a + b$

Q7

The Chinese Remainder Theorem states that if $m_1, m_2, \ldots, m_k$ are pairwise coprime integers, then the system of congruences $x \equiv a_i \pmod{m_i}$ for $i = 1, 2, \ldots, k$ has:

A unique solution modulo $M = m_1 m_2 \cdots m_k$ Exactly $k$ solutions modulo $M = m_1 m_2 \cdots m_k$ A solution if and only if $\gcd(m_i, m_j) = 1$ for all $i \neq j$ Infinitely many solutions

Q8

If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then which of the following is NOT necessarily true?

$a + c \equiv b + d \pmod{m}$ $a - c \equiv b - d \pmod{m}$ $ac \equiv bd \pmod{m}$ $a^c \equiv b^d \pmod{m}$

Q9

The linear congruence $ax \equiv b \pmod{m}$ has a solution if and only if:

$\gcd(a, m)$ divides $b$ $\gcd(a, b)$ divides $m$ $\gcd(a, m) = 1$ $\gcd(b, m) = 1$

Q10

Fermat's Little Theorem states that if $p$ is a prime number and $a$ is an integer not divisible by $p$, then:

$a^{p-1} \equiv 1 \pmod{p}$ $a^p \equiv a \pmod{p}$ $a^{p} \equiv 1 \pmod{p}$ Both (a) and (b)

Q11

Euler's theorem states that if $a$ and $n$ are coprime positive integers, then:

$a^{\phi(n)} \equiv 1 \pmod{n}$ where $\phi(n)$ is Euler's totient function $a^{n-1} \equiv 1 \pmod{n}$ $a^{\phi(n)} \equiv a \pmod{n}$ $a^n \equiv a \pmod{n}$

Q12

Wilson's theorem states that for a prime number $p$:

$(p-1)! \equiv -1 \pmod{p}$ $(p-1)! \equiv 1 \pmod{p}$ $(p-1)! \equiv 0 \pmod{p}$ $(p-1)! \equiv p-1 \pmod{p}$

Q13

For a prime number $p$ and positive integer $k$, the value of Euler's totient function $\phi(p^k)$ is:

$p^k - p^{k-1}$ $p^k - 1$ $p^{k-1}$ $p^k - k$

Q14

If $m$ and $n$ are coprime positive integers, then Euler's totient function satisfies:

$\phi(mn) = \phi(m)\phi(n)$ $\phi(m+n) = \phi(m) + \phi(n)$ $\phi(mn) = \phi(m) + \phi(n)$ $\phi(mn) = \phi(m)\phi(n) - \phi(\gcd(m,n))$

Q15

The Mobius function $\mu(n)$ is defined as:

$\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ (-1)^k & \text{if } n \text{ is a product of } k \text{ distinct primes} \\ 0 & \text{if } n \text{ has a squared prime factor} \end{cases}$ $\mu(n) = \begin{cases} 1 & \text{if } n \text{ is square-free with an even number of prime factors} \\ -1 & \text{if } n \text{ is square-free with an odd number of prime factors} \\ 0 & \text{if } n \text{ has a squared prime factor} \end{cases}$ $\mu(n) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n > 1 \end{cases}$ $\mu(n) = \begin{cases} 1 & \text{if } n \text{ is prime} \\ -1 & \text{if } n \text{ is composite} \\ 0 & \text{if } n = 1 \end{cases}$

Q16

The Mobius inversion formula states that if $g(n) = \sum_{d|n} f(d)$ for all positive integers $n$, then:

$f(n) = \sum_{d|n} \mu(d) g\left(\frac{n}{d}\right)$ $f(n) = \sum_{d|n} \mu\left(\frac{n}{d}\right) g(d)$ $f(n) = \sum_{d|n} \mu(d) g(d)$ $f(n) = \sum_{d|n} g\left(\frac{n}{d}\right)$

Q17

The sum of divisors function $\sigma(n)$ is defined as:

$\sigma(n) = \sum_{d|n} d$ (sum of all positive divisors of $n$) $\sigma(n) = \sum_{d|n, d < n} d$ (sum of proper divisors of $n$) $\sigma(n) = \sum_{d|n} \frac{n}{d}$ (sum of quotients when $n$ is divided by its divisors) $\sigma(n) = \sum_{d|n} \phi(d)$ (sum of Euler's totient function over divisors)

Q18

If $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$ is the prime factorization of $n$, then the number of positive divisors of $n$ is:

$(k_1 + 1)(k_2 + 1) \cdots (k_r + 1)$ $k_1 k_2 \cdots k_r$ $p_1 p_2 \cdots p_r$ $k_1 + k_2 + \cdots + k_r$

Q19

The linear Diophantine equation $ax + by = c$ has integer solutions if and only if:

$\gcd(a,b)$ divides $c$ $\gcd(a,c)$ divides $b$ $\gcd(b,c)$ divides $a$ $\gcd(a,b,c) = 1$

Q20

An integer $a$ is a quadratic residue modulo an odd prime $p$ if:

There exists an integer $x$ such that $x^2 \equiv a \pmod{p}$ There exists an integer $x$ such that $x^2 \equiv a \pmod{p}$ and $0 \leq x < p$ $a$ is a perfect square $a$ is coprime with $p$

Q21

The Legendre symbol $\left(\frac{a}{p}\right)$ for an odd prime $p$ and integer $a$ not divisible by $p$ is defined as:

$\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p \\ -1 & \text{if } a \text{ is a quadratic non-residue modulo } p \end{cases}$ $\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p \\ 0 & \text{if } a \text{ is a quadratic non-residue modulo } p \end{cases}$ $\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p \\ -1 & \text{if } a \text{ is a quadratic non-residue modulo } p \\ 0 & \text{if } p \text{ divides } a \end{cases}$ $\left(\frac{a}{p}\right) = a^{(p-1)/2} \pmod{p}$

Q22

The law of quadratic reciprocity states that for distinct odd primes $p$ and $q$:

$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$ $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$ $\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$ $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{pq}$

Q23

The Jacobi symbol $\left(\frac{a}{n}\right)$ for an odd positive integer $n$ and integer $a$ coprime to $n$ is defined as:

If $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$, then $\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{k_1} \left(\frac{a}{p_2}\right)^{k_2} \cdots \left(\frac{a}{p_r}\right)^{k_r}$ where $\left(\frac{a}{p_i}\right)$ are Legendre symbols $\left(\frac{a}{n}\right) = 1$ if and only if $a$ is a quadratic residue modulo $n$ $\left(\frac{a}{n}\right) = a^{(n-1)/2} \pmod{n}$ $\left(\frac{a}{n}\right) = \left(\frac{n}{a}\right)$ if $a$ is also an odd prime

Q24

A finite simple continued fraction has the form:

$a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots + \frac{1}{a_n}}}}$ where $a_0$ is an integer and $a_1, a_2, \ldots, a_n$ are positive integers $\frac{a_0}{a_1 + \frac{a_2}{a_3 + \frac{a_4}{\ddots + \frac{a_{n-1}}{a_n}}}}$ where $a_0, a_1, \ldots, a_n$ are positive integers $a_0 + \frac{a_1}{a_2} + \frac{a_3}{a_4} + \cdots + \frac{a_{n-1}}{a_n}$ where $a_0, a_1, \ldots, a_n$ are integers $\frac{1}{a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots + \frac{1}{a_n}}}}}$ where $a_0, a_1, \ldots, a_n$ are positive integers

Q25

The convergents of a continued fraction are:

The finite continued fractions obtained by truncating the expansion at each step The values of the partial denominators $a_0, a_1, \ldots, a_n$ The integers that appear in the continued fraction expansion The fractions obtained by reversing the order of the partial denominators

Q26

Which of the following numbers has a periodic continued fraction expansion?

$\sqrt{2}$ $\pi$ $e$ $\ln 2$

Q27

A perfect number is a positive integer that is equal to:

The sum of its proper divisors The sum of its prime factors The product of its proper divisors Twice the sum of its proper divisors

Q28

A Pythagorean triple consists of three positive integers $(a, b, c)$ such that:

$a^2 + b^2 = c^2$ $a + b = c$ $a^2 + b^2 + c^2 = 0$ $a + b + c = 0$

Q29

A primitive root modulo $m$ is an integer $g$ such that:

The multiplicative order of $g$ modulo $m$ is $\phi(m)$ $g$ is a generator of the multiplicative group of integers modulo $m$ $g^{\phi(m)} \equiv 1 \pmod{m}$ Both (a) and (b)

Q30

A quadratic form in two variables over the integers is an expression of the form:

$ax^2 + bxy + cy^2$ where $a, b, c$ are integers $ax^2 + by^2$ where $a, b$ are integers $ax^2 + bxy + cy^2 + dx + ey + f$ where $a, b, c, d, e, f$ are integers $ax^2 + bxy + cy^2 = 0$ where $a, b, c$ are integers

Quiz Results

0/30

Keep practicing!