CoprimeQ
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 all close allBasic Examples (2)
Scope (4)
CoprimeQ works over integers:
CoprimeQ[2, 3, -5, 7]CoprimeQ[5 + I, 1 - I]CoprimeQ[5, 7, GaussianIntegers -> True]CoprimeQ[2 ^ 100 - 1, 3 ^ 100 - 1]CoprimeQ threads elementwise over lists:
CoprimeQ[{1, 2, 3, 4, 5}, 6]Options (1)
Applications (8)
Basic Applications (3)
Highlight numbers that are coprime to 
:
Multicolumn[If[CoprimeQ[#, 12], Style[#, Red, Bold], #]& /@ Range[100], 10, ...]Generate random numbers coprime to a given number:
randomCoprime[x_Integer] := RandomChoice[Pick[Range[x], CoprimeQ[x, Range[x]]]];randomCoprime[15]CoprimeQ[15, %]Plot random pairs of coprime numbers:
ListPlot[{#, randomCoprime[#]}& /@ RandomInteger[{3, 100}, 500]]Visualize when two numbers are coprime:
ArrayPlot[Table[Boole[CoprimeQ[i, j]], {i, 50}, {j, 50}]]Number Theory (5)
Use CoprimeQ to compute Euler's totient function:
eulerPhi[n_] := Length[Select[Range[n], CoprimeQ[#, n] == True&]];ListPlot[Table[eulerPhi[n], {n, 100}]]Use CoprimeQ to check for trivial GCDs:
CoprimeQ[5, 6]GCD[5, 6]Find the fraction of pairs of the first 
numbers that are relatively prime:
Total[Boole[Array[CoprimeQ, {100, 100}]], 2] / 10 ^ 4//N
N[1 / Zeta[2]]Compute the modular inverse of coprime numbers:
CoprimeQ[5, 3]ModularInverse[5, 3]Use ExtendedGCD:
ExtendedGCD[5, 3][[2, 2]]Database encryption and decryption:
data = {145895125, 148963155, 789524465, 489325698, 598632147};keys = RandomPrime[{10 ^ 9, 10 ^ 12}, 5]CoprimeQ@@keysencrypted = ChineseRemainder[data, keys]Mod[encrypted, keys]Properties & Relations (9)
Coprime numbers have a greatest common divisor GCD equal to 
:
CoprimeQ[8, 9]GCD[8, 9]The least common multiple LCM of two coprime numbers is equal to their product:
CoprimeQ[6, 11]LCM[6, 11] == 6 11The number of divisors of a number preserves multiplication for coprime numbers:
CoprimeQ[5, 12]Length[Divisors[5]]Length[Divisors[12]] == Length[Divisors[5 12]]Coprime numbers a and b satisfy 
for some integers x and y:
a = 7;
b = 15;CoprimeQ[a, b]FindInstance[a * x + b * y == 1, {x, y}, Integers]The numbers 
and 
are the only integers coprime to every integer:
Table[CoprimeQ[1, n], {n, 10}]Table[CoprimeQ[-1, n], {n, 10}]Prime numbers are relatively prime to each other:
CoprimeQ[Prime[10], Prime[15], Prime[20], Prime[25]]EulerPhi gives the count of the positive integers up to n that are relatively prime to n:
EulerPhi[20]Coprime numbers a and n satisfy 
:
CoprimeQ[7, 10]PowerMod[7, EulerPhi[10], 10]If a and b are coprime, then so are any powers 
and 
:
a = 6;b = 25;CoprimeQ[a, b]Flatten[Table[CoprimeQ[a ^ k, b ^ m], {k, 3}, {m, 3}]]Neat Examples (2)
Plot numbers that are coprime:
ArrayMesh[Boole[Table[CoprimeQ[a, b, c], {a, 10}, {b, 10}, {c, 10}]]]Plot the Ulam spiral of a sequence of coprime numbers:
ulam[n_] := Partition[Permute[Range[n ^ 2], Accumulate[Take[Flatten[{{n ^ 2 + 1} / 2, Table
[(-1) ^ j i, {j, n}, {i, {-1, n}}, {j}]}], n ^ 2]]], n];ArrayPlot[Boole[CoprimeQ[ulam[101], ulam[101] ^ 15 + 9]], ColorFunction -> "Rainbow"]Text
Wolfram Research (2007), CoprimeQ, Wolfram Language function, https://reference.wolfram.com/language/ref/CoprimeQ.html.
CMS
Wolfram Language. 2007. "CoprimeQ." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/CoprimeQ.html.
APA
Wolfram Language. (2007). CoprimeQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/CoprimeQ.html