# 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 , 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: