Number theory

How many primitive roots are there modulo $13$?

Use quadratic reciprocity to compute the Legendre symbol $\left(\frac{37}{101}\right)$. (Enter $1$ or $-1$.)

For which moduli $n$ does a primitive root exist? (Select all that apply.)

Which of these numbers are sums of two squares of integers? (Select all that apply.)

In the proof of Euler's criterion, let $g$ be a primitive root modulo an odd prime $p$ and $a = g^k$. Why is $a^{(p-1)/2} \equiv 1$ exactly when $k$ is even?

Compute $\sum_{d \mid 60} \mu(d)$, where $\mu$ is the Möbius function.

The fundamental solution of $x^2 - 2y^2 = 1$ is $(3, 2)$. Using composition, $(x + y\sqrt2) = (3 + 2\sqrt2)^2$, find the next solution. What is its $x$?

In Lean, legendreSym p a is the Legendre symbol $\left(\frac{a}{p}\right)$. Which statement is the law of quadratic reciprocity for primes p, q (with [Fact p.Prime] [Fact q.Prime])?

Write order(a, n) returning the multiplicative order of $a$ modulo $n$ (assume $\gcd(a, n) = 1$, $n \ge 2$), and primitive_roots(p) returning the sorted list of primitive roots modulo a prime $p$. Check that there are $\varphi(p - 1)$ of them.