CoprimeQ

CoprimeQ[n1,n2]

yields True if n1 and n2 are relatively prime, and yields False otherwise.

CoprimeQ[n1,n2,]

yields True if all pairs of the ni are relatively prime, and yields False otherwise.

Details

  • CoprimeQ is typically used to test whether two numbers are relatively prime.
  • Integers are relatively prime if their greatest common divisor is 1.
  • CoprimeQ[n1,n2] returns False unless n1,n2 are manifestly relatively prime.
  • With the setting GaussianIntegers->True, CoprimeQ tests whether Gaussian integers are relatively prime.
  • CoprimeQ works over Gaussian integers.

Examples

open allclose all

Basic Examples  (2)

Test whether two numbers are relatively prime:

The numbers and are not relatively prime:

Scope  (4)

CoprimeQ works over integers:

Gaussian integers:

Test for large integers:

CoprimeQ threads elementwise over lists:

Options  (1)

GaussianIntegers  (1)

Test whether is composite over integers:

Gaussian integers:

Applications  (8)

Basic Applications  (3)

Highlight numbers that are coprime to :

Generate random numbers coprime to a given number:

Plot random pairs of coprime numbers:

Visualize when two numbers are coprime:

Number Theory  (5)

Use CoprimeQ to compute Euler's totient function:

Use CoprimeQ to check for trivial GCDs:

Find the fraction of pairs of the first numbers that are relatively prime:

The result is close to :

Compute the modular inverse of coprime numbers:

Use ExtendedGCD:

Database encryption and decryption:

Key generation:

Encrypted data:

Decrypted data:

Properties & Relations  (9)

Coprime numbers have a greatest common divisor GCD equal to :

The least common multiple LCM of two coprime numbers is equal to their product:

The number of divisors of a number preserves multiplication for coprime numbers:

Coprime numbers a and b satisfy for some integers x and y:

The numbers and are the only integers coprime to every integer:

Prime numbers are relatively prime to each other:

EulerPhi gives the count of the positive integers up to n that are relatively prime to n:

Coprime numbers a and n satisfy :

If a and b are coprime, then so are any powers and :

Neat Examples  (2)

Plot numbers that are coprime:

Plot the Ulam spiral of a sequence of coprime numbers:

Introduced in 2007
 (6.0)