Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 37 · Projects and Practice

Practice: Number Theory Problem Set

Ten number theory problems on primality, Diophantine equations, quadratic residues and cryptography, each with a runnable Python solution and hints.

Reading a proof teaches you what is true; solving problems teaches you how to use it. This set has ten problems drawn from the chapters on primality, Diophantine equations, quadratic residues and cryptography. Each has a hint, and a runnable solution that you should open only after a real attempt.

The most productive way to work: guess the structure with a small experiment, find the theorem that explains it, then write the efficient version. Every solution below has a brute-force check or an independent library check, so you can trust its output. Compare their printed answers with yours.

Problem 1: A very persistent liar

What is the smallest odd composite n that is a strong probable prime to both base 2 and base 3 (so Miller-Rabin with those two bases is fooled)?

Hint: write a strong-test function and scan upward through the odd composites. The answer is above one million.

Python Solution 1

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer, 1373653, is exactly the bound in the table of the Miller-Rabin lesson: below it, bases 2 and 3 are a deterministic test.

Problem 2: Carmichael census

How many Carmichael numbers are there below 100,000?

Hint: use Korselt's criterion from the Fermat test lesson: squarefree, composite, and p - 1 | n - 1 for each prime factor p.

Python Solution 2

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

(Carmichael numbers always have at least three prime factors; the check above uses that fact, which saves effort.) The list begins 561, 1105, 1729 and has 16 entries.

Problem 3: Stamps

Stamps cost 12 and 18 cents. How many ways are there to pay exactly 300 cents with non-negative numbers of each, and which amounts between 1 and 100 cannot be paid at all?

Hint: the answer to the second question depends only on gcd(12, 18). Count the first with the formula for non-negative solutions.

Python Solution 3

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every payable amount is a multiple of 6, but not every multiple of 6 works: after dividing by 6 the problem is 2x + 3y = n/6, whose Frobenius number is 2·3 - 2 - 3 = 1, so only n/6 = 1, i.e. 6 cents, is impossible among multiples of 6.

Problem 4: Triangles by perimeter

For perimeters up to 1000, which perimeter P is shared by the most distinct integer right triangles (a, b, c) with a + b + c = P?

Hint: generate triples from Euclid's formula and multiples of them, or simply brute force with the substitution c = P - a - b.

Python Solution 4

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The perimeter 840 carries 8 distinct right triangles, more than any other perimeter up to 1000, and the brute-force check lists them.

Problem 5: A stubborn Pell equation

Find the fundamental solution of x² - 991y² = 1. How many digits does x have?

Hint: brute force will never finish; use the continued fraction of √991.

Python Solution 5

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fundamental solution has 30 digits (about 3.8 × 10²⁹). It is one of the famously large cases.

Problem 6: Which primes like 10?

For how many primes p < 1000 is 10 a quadratic residue? By quadratic reciprocity it depends only on p modulo 40; find the residues.

Hint: 10 = 2·5, and the symbols (2/p) and (5/p) depend on p mod 8 and p mod 5.

Python Solution 6

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 82 of the 166 primes tested, 10 is a residue. The two printed lists of residues modulo 40 are disjoint, and together they cover all the classes coprime to 40 (there are 16 of them): the answer depends only on p mod 40, as reciprocity predicts.

Problem 7: A square root modulo a big prime

Compute the smaller square root of 2 modulo p = 10⁹ + 7 and check it.

Hint: p ≡ 7 (mod 8) so 2 is a residue; p ≡ 3 (mod 4) so the shortcut a^((p+1)/4) works.

Python Solution 7

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The square of the printed root is 2 modulo p, and SymPy agrees on the root.

Problem 8: Discrete logarithm

Find x with 2^x ≡ 777 (mod 1000003) and the order of 2 modulo this prime.

Hint: baby-step giant-step finds x in about a thousand steps.

Python Solution 8

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The reported x really satisfies 2^x ≡ 777, and SymPy's discrete_log returns the same exponent.

Problem 9: Rebuild a broken RSA key

You see the public key n = 1000000016000000063 and e = 65537, and a ciphertext produced from a short message number. Recover the message number m given c = m^e mod n with m = 123456789.

Hint: the modulus is the product of two ten-digit primes; both are very close to 10⁹. A one-line Fermat factorization finds them, then d = e⁻¹ mod φ(n).

Python Solution 9

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Close primes make Fermat's method succeed on the first step, and the decrypted value is 123456789.

Problem 10: Which numbers are sums of two squares?

How many integers n with 1 ≤ n ≤ 100000 are sums of two squares? Verify the theorem (primes 3 (mod 4) to even powers) against a direct search.

Hint: mark a² + b² in a boolean array for all a ≤ b.

Python Solution 10

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

24028 integers up to 100,000 qualify, roughly one in four. The density of sums of two squares decreases to zero like 1/√(ln n), so the share keeps shrinking, very slowly.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In Problem 2, why does a Carmichael number need at least three prime factors?

    If q - 1 divides pq - 1 = p(q - 1) + (p - 1), then q - 1 divides p - 1; symmetrically p - 1 divides q - 1, forcing p = q.
  2. 2. Which equation has solutions in integers?

    gcd(12, 18) = 6 divides 102, while 6 does not divide 100, 7 does not divide 50 and 5 does not divide 52.
  3. 3. Why was Fermat factorization instant in Problem 9?

    The search starts at ceil(sqrt n) and ends at the average of the two factors.
  4. 4. When is 2 a quadratic residue modulo an odd prime p?

    This is the second supplement of quadratic reciprocity.

Summary

  • Experiment first, then look for the theorem that explains the data.
  • Miller-Rabin base sets, Korselt's criterion, Euclid's formula, Pell's continued fractions and reciprocity each turned a hard search into a short calculation.
  • Always keep an independent check: brute force on a smaller range, or a library function.
  • Weak keys (close primes, small d, shared primes) fail to elementary arithmetic.

Next: back to the Number Theory track page for the other chapters.