Hints for Selected Problems
Write the two integers as
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.