# Hints for Selected Problems

## Hints for Problem Set 1. Foundations

### 1. Sum of Two Even Integers

Write the two integers as

$$
a=2m,\qquad b=2n.
$$

Then factor $2$ from $a+b$.

### 2. Product of Two Odd Integers

Write

$$
a=2m+1,\qquad b=2n+1.
$$

Expand $ab$, then show it has the form $2k+1$.

### 3. If $n^2$ Is Even, Then $n$ Is Even

Use proof by contrapositive.

Assume $n$ is odd. Then write

$$
n=2k+1.
$$

Show that $n^2$ is odd.

### 4. Sum of the First $n$ Integers

Use induction.

Base case:

$$
n=1.
$$

For the inductive step, add $n+1$ to both sides of

$$
1+2+\cdots+n=\frac{n(n+1)}{2}.
$$

### 5. Sum of Squares

Use induction.

Assume

$$
1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}.
$$

Then add $(n+1)^2$ and simplify until the expression becomes

$$
\frac{(n+1)(n+2)(2n+3)}{6}.
$$

### 6. Prime Divisor

Use strong induction.

If $n$ is prime, it divides itself. If $n$ is composite, write

$$
n=ab
$$

with

$$
1<a<n.
$$

Then apply the induction hypothesis to $a$.

### 7. Infinitely Many Primes

Assume there are finitely many primes

$$
p_1,\ldots,p_k.
$$

Consider

$$
N=p_1p_2\cdots p_k+1.
$$

No listed prime divides $N$. Now use the fact that every integer greater than $1$ has a prime divisor.

### 8. Transitivity of Divisibility

Use the definitions:

$$
a\mid b \implies b=ak,
$$

$$
b\mid c \implies c=b\ell.
$$

Substitute.

### 9. Linear Combination Property

Use

$$
b=am,\qquad c=an.
$$

Then compute

$$
bx+cy.
$$

### 10. GCD Identity

Show that the common divisors of $a,b$ are exactly the common divisors of $b,a-b$.

## Hints for Problem Set 2. Divisibility and Euclidean Algorithm

### 1. Compute $\gcd(252,198)$

Apply repeated division:

$$
252=198+54,
$$

$$
198=3\cdot54+36,
$$

and continue until the remainder is $0$.

### 2. Bézout Coefficients

Work backward through the Euclidean algorithm.

Express the final nonzero remainder as an integer combination of $252$ and $198$.

### 3. Bézout Identity

Prove that each remainder in the Euclidean algorithm is an integer combination of the original two numbers.

The last nonzero remainder is the gcd.

### 4. Euclid’s Lemma

Use Bézout’s identity.

If $\gcd(p,a)=1$, then

$$
px+ay=1.
$$

Multiply by $b$.

### 5. Uniqueness of Prime Factorization

Suppose

$$
p_1\cdots p_r=q_1\cdots q_s.
$$

Use Euclid’s lemma to show that $p_1$ equals one of the $q_i$. Cancel and continue.

### 6. Factorization of $5040$

Break it into familiar factors:

$$
5040=504\cdot10.
$$

Then factor $504$ and $10$.

### 7. GCD from Prime Factorizations

Use the minimum exponent of each prime appearing in both numbers.

### 8. LCM from Prime Factorizations

Use the maximum exponent of each prime appearing in either number.

### 9. GCD-LCM Formula

Compare prime exponents.

For each prime $p$, the exponent in the gcd plus the exponent in the lcm equals the exponent in $|ab|$.

### 10. Coprime Divisibility

Use Bézout:

$$
ax+by=1.
$$

Multiply by $c$, then use $a\mid bc$.

## Hints for Problem Set 3. Congruences

### 1. Equivalence Relation

Check reflexivity, symmetry, and transitivity directly from

$$
a\equiv b\pmod n
\iff
n\mid(a-b).
$$

### 2. Solve $3x\equiv7\pmod{11}$

Find the inverse of $3$ modulo $11$. Then multiply both sides by it.

### 3. Solve $12x\equiv8\pmod{20}$

First compute

$$
d=\gcd(12,20).
$$

A solution exists only if $d\mid8$. Then divide the congruence by $d$.

### 4. Inverse of $17$ Modulo $43$

Use the extended Euclidean algorithm to solve

$$
17x+43y=1.
$$

Then $x$ is the inverse modulo $43$.

### 5. Invertibility Criterion

If $a$ has inverse $b$, then

$$
ab\equiv1\pmod n.
$$

Translate this into a Bézout identity. Conversely, use Bézout to construct an inverse.

### 6. Chinese Remainder System

First combine the congruences modulo $3$ and $5$, then combine the result with the congruence modulo $7$.

### 7. CRT for Two Moduli

Use Bézout:

$$
mx+ny=1.
$$

Construct a solution from the two congruences using the coefficients $x,y$.

### 8. Compute $2^{100}\pmod{13}$

Use Fermat’s little theorem:

$$
2^{12}\equiv1\pmod{13}.
$$

Reduce $100$ modulo $12$.

### 9. Fermat’s Little Theorem

If $p\nmid a$, multiplication by $a$ permutes the nonzero residue classes modulo $p$.

Multiply all classes and cancel.

### 10. Compute $7^{222}\pmod{40}$

Since

$$
\gcd(7,40)=1,
$$

use Euler’s theorem. Compute $\varphi(40)$, then reduce $222$ modulo $\varphi(40)$.

## Hints for Problem Set 4. Arithmetic Functions

### 1. Compute $\varphi(n)$

Count integers $1\le k\le n$ with

$$
\gcd(k,n)=1.
$$

For larger $n$, use the prime factorization formula.

### 2. Totient of a Prime Power

The numbers not coprime to $p^k$ are exactly the multiples of $p$.

Count them.

### 3. Multiplicativity of $\varphi$

Use the Chinese remainder theorem:

$$
\mathbb{Z}/mn\mathbb{Z}
\cong
\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}
$$

when $\gcd(m,n)=1$.

### 4. Compute $\mu(n)$

Check whether $n$ is squarefree. If it is, count the number of distinct prime factors.

### 5. Sum of Möbius Function over Divisors

Use the prime factorization of $n$. The divisor sum becomes

$$
(1-1)^k
$$

when $n>1$.

### 6. Möbius Inversion

Start with

$$
g(n)=\sum_{d\mid n}f(d).
$$

Compute

$$
\sum_{d\mid n}\mu(d)g(n/d)
$$

and interchange the order of summation.

### 7. Sum of $\varphi(d)$ over Divisors of $60$

Use the theorem

$$
\sum_{d\mid n}\varphi(d)=n.
$$

Alternatively, list all divisors and compute directly.

### 8. Prove $\sum_{d\mid n}\varphi(d)=n$

Partition the integers

$$
1,2,\ldots,n
$$

according to the value of $\gcd(k,n)$.

### 9. Multiplicativity of $\tau(n)$

Use prime factorizations and the Chinese remainder structure of divisors for coprime factors.

### 10. Formula for $\tau(n)$

If

$$
n=p_1^{a_1}\cdots p_r^{a_r},
$$

then each divisor chooses an exponent between $0$ and $a_i$ for each prime $p_i$.

## Hints for Problem Set 5. Diophantine Equations

### 1. Linear Equation

Compute

$$
\gcd(35,21).
$$

The equation has integer solutions exactly when this gcd divides $14$.

### 2. Solve $15x+28y=1$

Use the extended Euclidean algorithm.

### 3. Primitive Pythagorean Triples

Use

$$
x^2+y^2=z^2.
$$

Assume one leg is even. Factor

$$
z^2-y^2=x^2
$$

as

$$
(z-y)(z+y)=x^2.
$$

### 4. Hypotenuse Less Than $50$

Use the standard parametrization:

$$
a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2.
$$

Require $\gcd(m,n)=1$ and opposite parity.

### 5. Pell Equation

Use continued fractions of $\sqrt{2}$, or use the recurrence generated by

$$
3+2\sqrt{2}.
$$

### 6. No Solution to $x^2\equiv3\pmod4$

List squares modulo $4$.

### 7. Prime Dividing a Sum of Squares

Assume

$$
p\mid x^2+y^2
$$

and $p\nmid y$. Then

$$
(xy^{-1})^2\equiv -1\pmod p.
$$

Use the fact that $-1$ is not a quadratic residue when $p\equiv3\pmod4$.

### 8. Solve $x^2-y^2=45$

Factor:

$$
(x-y)(x+y)=45.
$$

Analyze factor pairs with the same parity.

### 9. No Positive Solutions to $x^2=2y^2$

Use infinite descent or the parity argument from irrationality of $\sqrt{2}$.

### 10. Rational Points on the Unit Circle

Draw a line through $(-1,0)$ with rational slope $t$. Intersect it with

$$
x^2+y^2=1.
$$

Solve for $x,y$ in terms of $t$.

## Hints for Problem Set 6. Quadratic Residues

### 1. Residues Modulo $11$

Compute

$$
0^2,1^2,\ldots,10^2\pmod{11}.
$$

Use symmetry:

$$
a^2\equiv(-a)^2\pmod{11}.
$$

### 2. Legendre Symbols

Use direct residue lists or Euler’s criterion.

### 3. Euler’s Criterion

Work in the cyclic group

$$
(\mathbb{Z}/p\mathbb{Z})^\times.
$$

Squares are exactly the even powers of a generator.

### 4. Compute $\left(\frac{37}{101}\right)$

Apply quadratic reciprocity, then reduce the numerator modulo the denominator.

### 5. Solve $x^2\equiv10\pmod{13}$

Compute the Legendre symbol

$$
\left(\frac{10}{13}\right)
$$

or list the squares modulo $13$.

### 6. First Supplementary Law

Use Euler’s criterion:

$$
\left(\frac{-1}{p}\right)\equiv (-1)^{(p-1)/2}\pmod p.
$$

Since both sides are $\pm1$, the congruence determines equality.

### 7. Second Supplementary Law

Count signs in Gauss’s lemma for multiplication by $2$ modulo $p$.

### 8. Jacobi Symbol Warning

Find a composite modulus $n$ and an integer $a$ such that

$$
\left(\frac{a}{n}\right)=1
$$

but $a$ is not a square modulo $n$.

Try $n=15$.

### 9. Compute $\left(\frac{1001}{9907}\right)$

Factor

$$
1001=7\cdot 11\cdot 13.
$$

Use multiplicativity and quadratic reciprocity.

### 10. Solve $x^2\equiv1\pmod{35}$

Use the Chinese remainder theorem:

$$
x^2\equiv1\pmod5,\qquad x^2\equiv1\pmod7.
$$

Each has two solutions. Combine them.

## Hints for Problem Set 7. Analytic Number Theory

### 1. Harmonic Series

Group terms:

$$
\frac12+\left(\frac13+\frac14\right)+\left(\frac15+\cdots+\frac18\right)+\cdots.
$$

Each block is at least $1/2$.

### 2. Divergence of $\sum_p 1/p$

Use Euler’s product and compare with the harmonic series.

Taking logarithms is the standard route.

### 3. Absolute Convergence of Euler Product

For $\operatorname{Re}(s)>1$, compare

$$
\sum_p p^{-s}
$$

with

$$
\sum_{n=1}^{\infty} n^{-\operatorname{Re}(s)}.
$$

### 4. Euler Product Formula

Start from unique factorization. Expand

$$
\prod_p(1+p^{-s}+p^{-2s}+\cdots).
$$

### 5. Abel Summation

Write a sum involving $a_n f(n)$ in terms of the partial sums

$$
A(x)=\sum_{n\le x}a_n.
$$

Then imitate integration by parts.

### 6. Estimate $\sum_{n\le x}\log n$

This is

$$
\log(\lfloor x\rfloor!).
$$

Use comparison with the integral

$$
\int_1^x \log t\,dt.
$$

### 7. Show $\vartheta(x)\le\psi(x)$

Use definitions:

$$
\vartheta(x)=\sum_{p\le x}\log p,
$$

$$
\psi(x)=\sum_{p^k\le x}\log p.
$$

The second sum includes all terms in the first.

### 8. PNT Forms

Use:

$$
\pi(x)\sim \frac{x}{\log x},
$$

$$
\vartheta(x)\sim x,
$$

$$
\psi(x)\sim x.
$$

Then explain why these are equivalent with some work.

### 9. Orthogonality of Characters

Use the fact that characters are homomorphisms on the finite abelian group

$$
(\mathbb{Z}/q\mathbb{Z})^\times.
$$

Nontrivial characters sum to $0$.

### 10. Nonvanishing of $L(1,\chi)$

In Dirichlet’s proof, the logarithmic contribution from primes in arithmetic progressions is isolated using characters.

If $L(1,\chi)\ne0$, unwanted cancellation does not destroy the main term.

## Hints for Problem Set 8. Algebraic Number Theory

### 1. $\sqrt2$ Is an Algebraic Integer

It satisfies the monic polynomial

$$
x^2-2=0.
$$

### 2. $\frac12$ Is Not an Algebraic Integer

Use the rational root theorem: the only rational algebraic integers are ordinary integers.

### 3. Minimal Polynomial of $\sqrt2+\sqrt3$

Let

$$
x=\sqrt2+\sqrt3.
$$

Then

$$
x^2=5+2\sqrt6.
$$

Isolate $\sqrt6$, square again, and simplify.

### 4. Norm and Trace in Quadratic Fields

The conjugate of

$$
a+b\sqrt d
$$

is

$$
a-b\sqrt d.
$$

The norm is the product. The trace is the sum.

### 5. Units in $\mathbb{Z}[i]$

Use the norm

$$
N(a+bi)=a^2+b^2.
$$

A unit must have norm $1$.

### 6. Factor $5$ in $\mathbb{Z}[i]$

Use

$$
5=1^2+2^2.
$$

Then

$$
5=(1+2i)(1-2i).
$$

### 7. Failure of Unique Factorization

Use the classic example:

$$
6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5}).
$$

Show these factors are irreducible and not associates.

### 8. Dedekind Domain

Give the definition and use

$$
\mathcal{O}_K
$$

as the main example, where $K$ is a number field.

### 9. Ideals in $\mathbb{Z}$

Let $I\ne0$. Choose the least positive element $n\in I$. Use division with remainder to show

$$
I=n\mathbb{Z}.
$$

### 10. Ideals Restore Factorization

In a Dedekind domain, nonzero ideals factor uniquely into prime ideals, even when elements do not factor uniquely.

## Hints for Problem Set 9. Elliptic Curves and Modular Forms

### 1. Nonsingularity

For

$$
F(x,y)=y^2-x^3+4x,
$$

check whether

$$
F=F_x=F_y=0
$$

has a common solution.

### 2. Small Rational Points

Begin by testing small integer values of $x$. Check whether

$$
x^3+x+1
$$

is a square.

### 3. Group Law

A line through two points intersects a cubic in a third point. Reflect that third point across the $x$-axis.

### 4. Compute $P+Q$

Use the slope formula. For $P\ne Q$,

$$
m=\frac{y_2-y_1}{x_2-x_1}.
$$

Then apply the standard Weierstrass addition formulas.

### 5. Count Points over $\mathbb{F}_5$

For each

$$
x\in\mathbb{F}_5,
$$

compute

$$
x^3+x+1
$$

and count how many $y$ satisfy the equation. Add the point at infinity.

### 6. Hasse Bound

The bound has the form

$$
\left|\#E(\mathbb{F}_q)-(q+1)\right|\le 2\sqrt q.
$$

### 7. Modular Form

State the transformation rule under

$$
\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}
\in SL_2(\mathbb{Z}).
$$

### 8. Cusp Forms

A cusp form is a modular form that vanishes at the cusps.

For $q$-expansions, this usually means the constant term is $0$.

### 9. Hecke Operator

Describe Hecke operators as linear operators acting on spaces of modular forms and encoding arithmetic symmetries.

### 10. Modularity Theorem

Every elliptic curve over $\mathbb{Q}$ is modular: it corresponds to a modular form of weight $2$ and suitable level.

## Hints for Problem Set 10. Computational and Cryptographic Number Theory

### 1. Euclidean Algorithm

Repeatedly replace

$$
(a,b)
$$

by

$$
(b,a\bmod b)
$$

until $b=0$.

### 2. Extended Euclidean Algorithm

Track coefficients $x,y$ at each step so that every remainder is represented as

$$
ax+by.
$$

### 3. Fast Modular Exponentiation

Use the binary expansion of the exponent.

Repeatedly square the base and multiply into the result when the current bit is $1$.

### 4. Miller-Rabin

Write

$$
n-1=2^s d
$$

with $d$ odd. Test random bases $a$ using the standard strong probable prime conditions.

### 5. Pollard Rho

Use a polynomial iteration such as

$$
f(x)=x^2+1\pmod n.
$$

Compute

$$
\gcd(|x-y|,n)
$$

where $x$ and $y$ move at different speeds.

### 6. RSA Key Generation

Choose primes $p,q$, compute

$$
N=pq,
$$

$$
\varphi(N)=(p-1)(q-1).
$$

Choose $e$ coprime to $\varphi(N)$, then compute

$$
d\equiv e^{-1}\pmod{\varphi(N)}.
$$

### 7. RSA Correctness

Show that

$$
(m^e)^d\equiv m\pmod N.
$$

Use

$$
ed\equiv1\pmod{\varphi(N)}
$$

and argue modulo $p$ and modulo $q$.

### 8. Arithmetic in $\mathbb{F}_p$

Use ordinary integer arithmetic followed by reduction modulo $p$. Division by $a\ne0$ means multiplication by $a^{-1}$.

### 9. Elliptic Curve Point Addition

Implement the formulas for point doubling and addition separately. Include the point at infinity as the identity.

### 10. Cryptographic Hardness

Explain that public-key cryptography relies on operations that are easy in one direction and hard to reverse without secret information.