0Pricing
Cryptology Academy · Lesson

GCD, Euler's Totient & Number Theory Intro

Apply GCD and Euler's totient function to real crypto problems.

GCD, Euler's Totient & Number Theory Intro is a free Cryptology Academy lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Cryptology Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

Welcome

The GCD and Euler's totient function are essential tools in RSA and many other public-key systems. Let's master them with examples.

Greatest Common Divisor (GCD)

GCD(a, b) is the largest integer that divides both a and b without remainder. GCD(12, 8) = 4. If GCD(a, m) = 1, we say a and m are coprime or relatively prime.

Euclidean Algorithm

GCD(a, b) = GCD(b, a mod b), base case GCD(a, 0) = a. GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

Extended Euclidean Algorithm

The extended version finds integers x, y such that ax + by = GCD(a,b). When GCD(a,m)=1, x is the modular inverse of a mod m. This is how RSA computes private keys.

Euler's Totient Function φ(n)

φ(n) counts integers from 1 to n that are coprime to n. φ(10) = 4 because {1, 3, 7, 9} are coprime to 10. φ(p) = p-1 for any prime p.

Totient of a Product

For RSA: n = p×q (p,q prime). φ(n) = φ(p)×φ(q) = (p-1)(q-1). Example: p=5, q=11: φ(55) = 4×10 = 40. This is why factoring n breaks RSA — it reveals φ(n).

Euler's Theorem

If GCD(a,n)=1: a^φ(n) ≡ 1 (mod n). This is the mathematical basis for RSA decryption: M = C^d mod n because e×d ≡ 1 (mod φ(n)).

Computing d in RSA

Choose e = 65537 (common RSA public exponent). Compute d = e^(-1) mod φ(n) using extended Euclidean. Verify e×d mod φ(n) == 1.

Totient in Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Carmichael's Lambda

Modern RSA uses Carmichael's lambda function λ(n) = lcm(p-1, q-1) instead of φ(n). It gives a smaller, equivalent modulus. PKCS#1 v2 and NIST recommend λ(n).

Practical Application Summary

GCD: verify coprimality of e with φ(n). Extended Euclidean: compute private key d. Totient: determine the exponent group for modular exponentiation. All three are used in every RSA key generation.

Quick Check

For RSA with p=7 and q=11, what is φ(n)?

Recap

Excellent! GCD, Euclidean algorithm, and Euler's totient are now in your toolkit. Next we study XOR and bitwise operations — the building blocks of symmetric ciphers.

Frequently asked questions

Is the “GCD, Euler's Totient & Number Theory Intro” lesson free?

Yes — the full text of “GCD, Euler's Totient & Number Theory Intro” is free to read here on the web, and the Cryptology Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Cryptology Academy course, upgrade to CoddyKit PRO.

What will I learn in “GCD, Euler's Totient & Number Theory Intro”?

Apply GCD and Euler's totient function to real crypto problems. You practise Cryptology Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Cryptology Academy?

No prior experience is required. Cryptology Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “GCD, Euler's Totient & Number Theory Intro” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Cryptology Academy lesson?

Yes. Every Cryptology Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

  1. Binary & Hexadecimal Fundamentals
  2. Modular Arithmetic Basics
  3. Prime Numbers & Factorization
  4. GCD, Euler's Totient & Number Theory Intro
← Back to Cryptology Academy