NUMBER THEORYArithmeticMathematics Calculator
๐Ÿ”ข

Relatively Prime: gcd(a,b) = 1

Two numbers are coprime (relatively prime) if gcd(a,b)=1. No common prime factors. Euler totient ฯ†(n) counts integers 1..n-1 coprime to n.

Concept Fundamentals
gcd=1
Coprime
gcd(8,9)=1
8,9
Euler totient
ฯ†(n)
gcd algorithm
Euclidean

Did our AI summary help? Let us know.

gcd(a,b)=1 โ‡” no common prime factors. 8 and 9 are coprime. ฯ†(p)=p-1 for prime p. ฯ†(10)=4 (1,3,7,9). Euclidean algorithm: gcd(a,b)=gcd(b, a mod b).

Key quantities
gcd=1
Coprime
Key relation
gcd(8,9)=1
8,9
Key relation
Euler totient
ฯ†(n)
Key relation
gcd algorithm
Euclidean
Key relation

Ready to run the numbers?

Why: Coprime numbers share no common factors. Used in RSA (e and ฯ†(n) must be coprime), fractions in lowest terms, and the Chinese remainder theorem.

How: Compute gcd(a,b). If gcd=1, they are coprime. Euclidean algorithm: gcd(a,b)=gcd(b, a mod b). For ฯ†(n): count integers in 1..n-1 with gcd(k,n)=1.

gcd(a,b)=1 โ‡” no common prime factors. 8 and 9 are coprime.ฯ†(p)=p-1 for prime p. ฯ†(10)=4 (1,3,7,9).
Sources:Khan AcademyMathWorld

Run the calculator when you are ready.

Check Relatively PrimeEnter integers

Enter Numbers

coprime.sh
CALCULATED
$ coprime --numbers 15, 28
Result
Coprime โœ“
GCD
1
Numbers
15, 28
GCD(15, 28)
15 = 28 ร— 0 + 15
28 = 15 ร— 1 + 13
15 = 13 ร— 1 + 2
13 = 2 ร— 6 + 1
2 = 1 ร— 2 + 0
GCD = 1
Relatively Prime Calculator
Coprime โœ“ (GCD = 1)
Numbers: 15, 28
numbervibe.com
Share:

Input Values

Result

๐Ÿ“ Step-by-Step Breakdown

SETUP
Numbers
15, 28
GCD
1
RESULT
Result
Relatively prime (coprime) โœ“

For educational and informational purposes only. Verify with a qualified professional.

๐Ÿงฎ Fascinating Math Facts

๐Ÿ”ข

Coprime: gcd(a,b)=1

โ€” Definition

ฯ†

ฯ†(n) = count coprime to n

โ€” Euler totient

๐Ÿ“‹ Key Takeaways

  • โ€ข Relatively prime (coprime): GCD(a, b, ...) = 1 โ€” no common factors except 1
  • โ€ข Euclidean algorithm: gcd(a,b) = gcd(b, a mod b). Efficient O(log n)
  • โ€ข Euler totient ฯ†(n): count of integers 1 to n coprime to n
  • โ€ข Consecutive integers are always coprime: gcd(n, n+1) = 1
  • โ€ข Two distinct primes are always coprime

๐Ÿ’ก Did You Know?

๐Ÿ”RSA cryptography relies on choosing coprime numbers for key generation.Source: Cryptography
๐Ÿ“Consecutive integers (n, n+1) are always coprime. gcd(n, n+1)=1.Source: Number Theory
โœจTwo distinct primes are always coprime. gcd(7,11)=1.Source: Primes
๐Ÿ“ŠProbability two random integers are coprime โ‰ˆ 6/ฯ€ยฒ โ‰ˆ 61%.Source: Probability
๐Ÿ”ขFraction a/b in lowest terms when gcd(a,b)=1.Source: Fractions
๐Ÿ“–Euclidean algorithm is 2300+ years old โ€” still the standard for GCD.Source: Euclid's Elements

๐Ÿ“– How It Works

Enter two or more integers. The calculator finds their GCD using the Euclidean algorithm: gcd(a,b) = gcd(b, a mod b), repeated until the remainder is 0. If GCD = 1, the numbers are relatively prime (coprime). Euler totient ฯ†(n) counts integers from 1 to n that are coprime to n. For prime p: ฯ†(p) = pโˆ’1.

๐Ÿ“ Worked Example: 15 and 28

Euclidean algorithm:

28 = 1 ร— 15 + 13 โ†’ gcd(15, 13)

15 = 1 ร— 13 + 2 โ†’ gcd(13, 2)

13 = 6 ร— 2 + 1 โ†’ gcd(2, 1)

2 = 2 ร— 1 + 0 โ†’ gcd(1, 0) = 1

15 and 28 are coprime.

Prime factors: 15=3ร—5, 28=4ร—7. No shared primes. โœ“

๐Ÿš€ Real-World Applications

๐Ÿ” RSA Cryptography

Keys use coprime e and ฯ†(n). Security relies on gcd.

๐Ÿ“ Fractions

Lowest terms: gcd(num, den)=1. 12/35 already reduced.

๐Ÿ“Š Chinese Remainder

CRT requires coprime moduli for unique solution.

๐ŸŽฒ Random Numbers

Linear congruential generators use coprime modulus.

๐Ÿ”ฌ Music Theory

Coprime periods in rhythm: no sync until LCM.

๐Ÿ’ป Hash Tables

Table size coprime to step size for full coverage.

โš ๏ธ Common Mistakes to Avoid

  • Confusing coprime with prime: Coprime = gcd(a,b)=1. Prime = number with 2 divisors.
  • Stopping Euclidean too early: Continue until remainder is 0. Last non-zero = GCD.
  • Negative numbers: GCD uses absolute values. gcd(-15, 28) = gcd(15, 28) = 1.
  • Three or more: gcd(a,b,c)=1 means all are coprime as a set. gcd(gcd(a,b),c)=1.
  • ฯ†(1) = 1: 1 is coprime to itself. ฯ†(1)=1 by convention.

๐ŸŽฏ Expert Tips

๐Ÿ’ก Euclidean Algorithm

gcd(a,b) = gcd(b, a mod b). Repeat until b=0. Then gcd=a.

๐Ÿ’ก Multiple Numbers

gcd(a,b,c) = gcd(gcd(a,b), c). Apply pairwise.

๐Ÿ’ก Prime Factors

Coprime = no shared prime factors. 15=3ร—5, 28=4ร—7 โ†’ no overlap.

๐Ÿ’ก Bรฉzout

If gcd(a,b)=1, then ax+by=1 for some integers x,y. Extended Euclidean finds them.

๐Ÿ“Š Reference Table

ConceptDefinition
Coprimegcd(a,b) = 1
Euclideangcd(a,b) = gcd(b, a mod b)
Euler ฯ†(n)Count of 1..n coprime to n
ฯ†(p) for primeฯ†(p) = p โˆ’ 1
Consecutivegcd(n, n+1) = 1

๐Ÿ“ Quick Reference

1
Coprime = GCD 1
6/ฯ€ยฒ
P(coprime) โ‰ˆ 61%
ฯ†(n)
Euler totient
n, n+1
Always coprime

๐ŸŽ“ Practice Problems

Are 14 and 25 coprime? โ†’ Yes (gcd=1)
Are 18 and 24 coprime? โ†’ No (gcd=6)
ฯ†(12) = ? โ†’ 4 (1,5,7,11)
gcd(100, 63) = ? โ†’ 1 (coprime)

โ“ FAQ

What does relatively prime mean?

Numbers with GCD = 1. No common factors except 1. Also called coprime.

Are 15 and 28 coprime?

Yes. 15=3ร—5, 28=4ร—7. No shared primes. GCD=1.

What is Euler totient?

ฯ†(n) = number of integers 1 to n that are coprime to n. ฯ†(12)=4 (1,5,7,11).

How does Euclidean algorithm work?

gcd(a,b)=gcd(b,a mod b). Repeat until b=0. Then gcd=a.

Applications?

Cryptography (RSA), fractions in lowest terms, Chinese Remainder Theorem.

Consecutive integers?

Any two consecutive integers (n, n+1) are always coprime.

Three or more numbers?

gcd(a,b,c)=gcd(gcd(a,b),c). If result is 1, the set is coprime.

๐Ÿ“Œ Summary

Relatively prime (coprime) means GCD = 1. Use the Euclidean algorithm to find GCD efficiently. Euler totient ฯ†(n) counts coprimes to n. Essential for cryptography, fractions, and number theory.

โœ… Verification Tip

For coprime: gcd should be 1. Check prime factors: no overlap. For ฯ†(n): list 1..n, count those with gcd(k,n)=1.

๐Ÿ”— Next Steps

Explore the GCF Calculator for greatest common divisor. The Prime Number Calculator checks primality. The Chinese Remainder Theorem uses coprime moduli.

โš ๏ธ Disclaimer: For educational use. Integer inputs only.

๐Ÿ‘ˆ START HERE
โฌ…๏ธJump in and explore the concept!
AI

Related Calculators

GCF Calculator

Find the greatest common factor (GCF/GCD) of two or more positive integers. Uses Euclidean algorithm with step-by-step breakdown. Prime factorization method...

Mathematics

Extended Euclidean Algorithm Calculator

Find gcd(a,b) and Bรฉzout coefficients x, y such that ax + by = gcd(a,b). Step-by-step division table. Modular inverse, linear Diophantine equations.

Mathematics

Multiplicative Inverse Modulo Calculator

Find the multiplicative inverse of a modulo m: aร—x โ‰ก 1 (mod m). Uses the Extended Euclidean Algorithm with step-by-step trace. Applications in cryptography (RSA, Diffie-Hellman), linear congruences, and Chinese Remainder Theorem. Verify with Fermat's Little Theorem for prime moduli.

Mathematics

Root Mean Square Calculator

Calculate RMS = sqrt(mean of xยฒ). AC voltage equivalent, compare with arithmetic mean. Step-by-step for statistics and signal processing.

Mathematics

Chinese Remainder Theorem Calculator

Solve systems of congruence equations x โ‰ก a_i (mod m_i) using the Chinese Remainder Theorem. Step-by-step solution with multiple moduli, modular inverse, and...

Mathematics

Consecutive Integers Calculator

Find n consecutive integers that sum to a target, or compute sum and product of consecutive integers. Supports even and odd consecutive sequences....

Mathematics