β„­π”―π”Άπ”­π”±π”¬π”€π”―π”žπ”­π”₯𝔦𝔠 𝔗𝔬𝔬𝔩𝔰 π”žπ”«π”‘ β„­π”žπ”©π” π”²π”©π”žπ”±π”¬π”―π”°

Number Theory Calculators

×

Greatest Common Divisor (GCD)

How to Use

Enter two or more positive integers. Use ⁜ to add another pair of input fields and βŠ– to remove the last pair. The GCD value updates dynamically as inputs are entered.

Understanding the Greatest Common Divisor (GCD)

The GCD is the largest integer that divides all given numbers. For example, the GCD of 8 and 12 is 4, because 4 is the largest integer that divides both numbers (8 and 12). The GCD widely used for simplifying fractions, modular arithmetic, and cryptographic algorithms, such as checking coprimality, finding the modular multiplicative inverse of a unit, and detecting weak randomness of public RSA keys by computing pairwise GCD's of those keys to find shared prime numbers.

×

Least Common Multiple (LCM)

How to Use

Enter two or more positive integers. Use ⁜ to add another pair of input fields and βŠ– to remove the last pair. The LCM value updates dynamically as inputs are entered.

Understanding the Least Common Multiple (LCM)

The LCM is the smallest positive integer that is divisible by all given numbers. For example, the LCM of 4 and 6 is 12, because 12 is the smallest integer that divides both numbers (4 and 6). The LCM is used for aligning cycles and working with common denominators. It is also used in RSA key generation to compute the Carmichael function πœ†(𝑛), which is equal to the LCM of (𝑝 - 1) and (π‘ž - 1), where 𝑝 and π‘ž are distinct semiprimes: πœ†(𝑛) = (𝑝 - 1, π‘ž - 1).

×

Modular Congruence

How to Use

Enter integers base π‘Ž and modulus π‘š. The least non‑negative residue of π‘Ž modulo π‘š updates dynamically as inputs are entered.

Understanding Modular Congruence

Modulo returns the remainder after division. For example, 21 mod 5 = 1 because 21 = 4 Γ— 5 + 1. Think of modulo as modulating the base by the modulus: that is, taking away (subtracting) the value of the modulus from the base until the base is less than the modulus. The least residue of every base smaller than the modulus is the value of that same base: 5 mod 15 = 5. Modular arithmetic is foundational in cryptography and number theory.

×

Modular Power

How to Use

Enter integers base π‘Ž, exponent 𝑏, and modulus π‘š. The 𝑏th power of π‘Ž mod π‘š (π‘Ž raised to the 𝑏th power modulo π‘š) updates dynamically as inputs are entered.

Understanding Modular Power

Modular exponentiation computes a multiplicative power while reducing the result modulo π‘š at every intermediate step along the way. Modular exponentiation is critical in RSA, Diffie‑Hellman, and many primality-related algorithms.

×

Modular Multiplicative Inverse

How to Use

Enter integers base π‘Ž and modulus π‘š. The modular multiplicative inverse of π‘Ž modulo π‘š is updated dynamically as inputs are entered.

Understanding the Modular Multiplicative Inverse

The modular inverse β€œundoes” multiplication modulo π‘š. It is analogous to division in modular arithmetic. For example, the inverse of 3 mod 11 is 4 since 3 Γ— 4 = 12 ≑ 1 (mod 11). An inverse exists only when the GCD of π‘Ž and is 1. An invertible base element is called a unit. Modular multiplicative inverses are key building blocks in RSA and modular equation solving.

×

Primality

How to Use

Enter a positive integer 𝑛. The primality thereof (whether 𝑛 is prime or composite) is updated dynamically as input is entered.

Understanding Primality

A prime number has exactly two positive divisors: the numbers 1 and itself. Prime numbers (primes) are central to number theory and asymmetric (public‑key) cryptography.

×

Phi Function

How to Use

Enter integer 𝑛. Phi of 𝑛 is updated dynamically as input is entered.

Understanding Phi Function

The phi function, also known as the totient function or Euler's phi (or totient) function, counts the number of integers relatively prime (coprime, sharing no common factors) to 𝑛. For any prime number 𝑝, Ο†(𝑝) is always equal to 𝑝 βˆ’ 1.

×

Multiplicative Order

How to Use

Enter integers base π‘Ž and modulus 𝑛. The multiplicative order of π‘Ž modulo 𝑛 is updated dynamically as inputs are entered.

Understanding Multiplicative Order

The multiplicative order counts how many powers of π‘Ž are needed (mod 𝑛) to get back to 1: the smallest π‘˜ > 0 such that π‘Ž^π‘˜ ≑ 1 (mod 𝑛). This requires that the GCD of π‘Ž and 𝑛 be equal to 1. The multiplicative order is a core concept in cyclic groups and discrete-log-based cryptography.

×

Discrete Logarithm

How to Use

Enter integers base π‘Ž, modular power 𝑏, and modulus π‘š. The index of 𝑏 to the base π‘Ž modulo π‘š is updated dynamically as inputs are entered.

Understanding the Discrete Logarithm

The discrete logarithm is the inverse of modular exponentiation: modular deponentation. Finding an index π‘₯ such that π‘Ž^π‘₯ ≑ 𝑏 (mod π‘š) is believed to be hard for large moduli, which is why it underpins Diffie‑Hellman and related cryptosystems.

×

Prime Factorization

How to Use

Enter 𝑛. The prime factorization of 𝑛 is updated dynamically as input is entered.

Understanding the Prime Factorization

Every integer greater than 1 has a unique prime factorization (decomposition into a product of prime powers, unique up to the ordering of factors). Factoring large integers is computationally difficult, which is central to cryptographic security.

×

Quadratic Residuosity

How to Use

Enter integers quadratic residue candidate π‘ž and modulus 𝑛. The quadratic residuosity of π‘ž mod 𝑛 is updated dynamically as inputs are entered.

Understanding Quadratic Residuosity

A quadratic residue candidate π‘ž is a quadratic residue mod 𝑛 if it is congruent to a square modulo 𝑛: π‘₯Β² ≑ π‘ž (mod 𝑛). Quadratic residuosity shows up in number theory, cryptographic constructions, and zero-knowledge protocols.

×

Coprime Modular Congruence System

How to Use

Enter integer residues π‘Žα΅’ and pairwise-coprime moduli 𝑛ᡒ. Use ⁜ to add another equation, and βŠ– to take away one. The unique base solving all the congruences (the unique solution modulo the product of all the moduli) is updated dynamically as equations are entered.

Understanding the Coprime Modular Congruence System

The Chinese Remainder Theorem (CRT) guarantees a unique solution modulo 𝑁 = ∏ 𝑛ᡒ (𝑁 being the product of all moduli) when the moduli are pairwise coprime. It is used in many computational and cryptographic searches and optimizations.

×

Least Primitive Root

How to Use

Enter integer modulus 𝑛. The least primitive root (generator) of 𝑛, when one exists, is updated dynamically as input is entered.

Understanding the Least Primitive Root

A primitive root modulo 𝑛 is an element whose powers generate all numbers coprime to 𝑛. Primitive roots exist only for certain moduli and are central to Diffie‑Hellman-style constructions.

π‘₯ΒΉ ≑

π‘₯Β² ≑

Great and unsearchable things, wonders without number …

EN | ES