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)$

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

(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

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)

(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.

Hints for Selected Problems

Hints for Problem Set 1. Foundations

1. Sum of Two Even Integers

2. Product of Two Odd Integers

3. If n2n^2n2 Is Even, Then nnn Is Even

4. Sum of the First nnn Integers

5. Sum of Squares

6. Prime Divisor

7. Infinitely Many Primes

8. Transitivity of Divisibility

9. Linear Combination Property

10. GCD Identity

Hints for Problem Set 2. Divisibility and Euclidean Algorithm

1. Compute gcd⁡(252,198)\gcd(252,198)gcd(252,198)

2. Bézout Coefficients

3. Bézout Identity

4. Euclid’s Lemma

5. Uniqueness of Prime Factorization

6. Factorization of 504050405040

7. GCD from Prime Factorizations

8. LCM from Prime Factorizations

9. GCD-LCM Formula

10. Coprime Divisibility

Hints for Problem Set 3. Congruences

1. Equivalence Relation

2. Solve 3x≡7(mod11)3x\equiv7\pmod{11}3x≡7(mod11)

3. Solve 12x≡8(mod20)12x\equiv8\pmod{20}12x≡8(mod20)

4. Inverse of 171717 Modulo 434343

5. Invertibility Criterion

6. Chinese Remainder System

7. CRT for Two Moduli

8. Compute 2100(mod13)2^{100}\pmod{13}2100(mod13)

9. Fermat’s Little Theorem

10. Compute 7222(mod40)7^{222}\pmod{40}7222(mod40)

Hints for Problem Set 4. Arithmetic Functions

1. Compute φ(n)\varphi(n)φ(n)

2. Totient of a Prime Power

3. Multiplicativity of φ\varphiφ

4. Compute μ(n)\mu(n)μ(n)

5. Sum of Möbius Function over Divisors

6. Möbius Inversion

7. Sum of φ(d)\varphi(d)φ(d) over Divisors of 606060

8. Prove ∑d∣nφ(d)=n\sum_{d\mid n}\varphi(d)=n∑d∣n​φ(d)=n

9. Multiplicativity of τ(n)\tau(n)τ(n)

10. Formula for τ(n)\tau(n)τ(n)

Hints for Problem Set 5. Diophantine Equations

1. Linear Equation

2. Solve 15x+28y=115x+28y=115x+28y=1

3. Primitive Pythagorean Triples

4. Hypotenuse Less Than 505050

5. Pell Equation

6. No Solution to x2≡3(mod4)x^2\equiv3\pmod4x2≡3(mod4)

7. Prime Dividing a Sum of Squares

8. Solve x2−y2=45x^2-y^2=45x2−y2=45

9. No Positive Solutions to x2=2y2x^2=2y^2x2=2y2

10. Rational Points on the Unit Circle

Hints for Problem Set 6. Quadratic Residues

1. Residues Modulo 111111

2. Legendre Symbols

3. Euler’s Criterion

4. Compute (37101)\left(\frac{37}{101}\right)(10137​)

5. Solve x2≡10(mod13)x^2\equiv10\pmod{13}x2≡10(mod13)

6. First Supplementary Law

7. Second Supplementary Law

8. Jacobi Symbol Warning

9. Compute (10019907)\left(\frac{1001}{9907}\right)(99071001​)

10. Solve x2≡1(mod35)x^2\equiv1\pmod{35}x2≡1(mod35)

Hints for Problem Set 7. Analytic Number Theory

1. Harmonic Series

2. Divergence of ∑p1/p\sum_p 1/p∑p​1/p

3. Absolute Convergence of Euler Product

4. Euler Product Formula

5. Abel Summation

6. Estimate ∑n≤xlog⁡n\sum_{n\le x}\log n∑n≤x​logn

7. Show ϑ(x)≤ψ(x)\vartheta(x)\le\psi(x)ϑ(x)≤ψ(x)

8. PNT Forms

9. Orthogonality of Characters

10. Nonvanishing of L(1,χ)L(1,\chi)L(1,χ)

Hints for Problem Set 8. Algebraic Number Theory

1. 2\sqrt22​ Is an Algebraic Integer

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

4. Sum of the First $n$ Integers

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

6. Factorization of $5040$

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

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

4. Inverse of $17$ Modulo $43$

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

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

1. Compute $\varphi(n)$

3. Multiplicativity of $\varphi$

4. Compute $\mu(n)$

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

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

9. Multiplicativity of $\tau(n)$

10. Formula for $\tau(n)$

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

4. Hypotenuse Less Than $50$

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

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

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

1. Residues Modulo $11$

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

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

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

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

2. Divergence of $\sum_p 1/p$

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

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

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

1. $\sqrt2$ Is an Algebraic Integer

2. $\frac12$ Is Not an Algebraic Integer

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

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

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

9. Ideals in $\mathbb{Z}$

4. Compute $P+Q$

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

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