Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 37 ยท Getting Started

Number Theory in Python

Set up your Python toolbox for number theory: arbitrary-size integers, divmod, three-argument pow, the math module, and the sympy.ntheory functions to check your own code.

You do not need special software to do number theory: Python already has most of the tools. Its int type has unlimited size, the math module has gcd, lcm, isqrt and comb, and the built-in pow can do modular exponentiation in a single call. For checking your own implementations, the sympy library offers ready-made functions for primes, factoring and more.

This lesson collects those tools in one place. The rest of the course implements each idea from scratch first, since that is how you learn it, and then compares the result with the library function.

Big integers

Python integers grow as needed. There is no overflow and no long type to remember.

Python Integers without limits

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.

Two operators matter most. // is floor division and % is the remainder; divmod(a, b) returns both. ** raises to a power. The result of / is always a float, so avoid it for exact work: 10**20 / 3 loses digits, while 10**20 // 3 is exact.

Float arithmetic is inexact beyond 2^53. Writing int(n ** 0.5) for the square root of a large integer can be off by one. Use math.isqrt(n), which is exact for any size.

Python Why isqrt matters

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 standard library

The functions you will use constantly are these.

Tool What it does
divmod(a, b) quotient and remainder
math.gcd(a, b, ...) greatest common divisor
math.lcm(a, b, ...) least common multiple
math.isqrt(n) exact integer square root
math.comb(n, k), math.factorial(n) binomial coefficients and factorials
pow(a, e, m) a to the power e, modulo m
pow(a, -1, m) modular inverse (if it exists)
n.bit_length() number of binary digits

The three-argument pow is the star. It computes a ** e % m without ever building the enormous number a**e: it squares and reduces as it goes (you will implement this yourself in Modular Arithmetic in Practice).

Python pow with a modulus

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.

Checking yourself with sympy

sympy.ntheory has hundreds of number-theory functions. They are useful as an independent check: write your own is_prime, then compare it with sympy.isprime over a range of inputs. Here are the most common ones.

Python A tour of sympy.ntheory

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.

On this site import sympy is loaded on demand when you press Run, so the first run is slower. In a normal Python install you would run pip install sympy once.

Verify against a library

A habit worth building: whenever you write a function, test it against a trusted one on many inputs. Disagreement means a bug.

Python Test your own is_prime

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.

Plotting patterns

Pictures reveal structure that lists hide. The matplotlib library works in the browser too. A famous example is the Ulam spiral, where primes written on a square spiral line up along diagonals. We will keep it small here.

Python Remainder pattern picture

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.

Notice that only certain values of a ever appear: those coprime to 12. That observation is the seed of modular inverses, which come later.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which call gives an exact integer square root of a very large integer n?

    math.isqrt works on integers exactly, while float-based roots are inexact above about 2^53.
  2. 2. What does pow(a, e, m) compute?

    Three-argument pow performs modular exponentiation efficiently by reducing at every step.
  3. 3. What happens with pow(6, -1, 9)?

    gcd(6, 9) = 3, not 1, so no modular inverse exists.
  4. 4. Why compare your own function with sympy's?

    Agreement on many inputs is good evidence your implementation is right; disagreement points to a bug.

Summary

  • Python integers have unlimited size; use //, %, divmod and ** for exact work and avoid /.
  • Use math.isqrt for exact square roots.
  • math.gcd, math.lcm, pow(a, e, m) and pow(a, -1, m) cover many tasks.
  • sympy.ntheory provides primes, factoring, divisors and totients for cross-checking.
  • Always test your own implementation against a library.

Next: Proofs in Number Theory