# getPrimeWithRootOfUnity -- find a prime p with a primitive n-th root of unity r in ZZ/p

## Synopsis

• Usage:
(p,r)=getPrimeWithRootOfUnity(n,r1)
• Inputs:
• n, an integer, the exponent of the root of unity
• r1, an integer, tentative root of unity
• Optional inputs:
• Range => , default value (10000,30000), of integers (a,b)
• Outputs:
• p, an integer, a prime in the specified range. The default range is $(10^4,3*10^4)$
• r, an integer, a primitive n-th root of unity mod p

## Description

We compute the prime p as a larger prime factor of $r1^n-1$. If the largest p in the desired range does not work, we pass to $r1+1$ and repeat.

 i1 : n = 12 o1 = 12 i2 : (p,r) = getPrimeWithRootOfUnity(n,5) o2 = (20593, 12) o2 : Sequence i3 : factor(r^n-1) o3 = 5*7*11*13*19*29*157*20593 o3 : Expression of class Product i4 : r^12%p==1, r^6%p==1, r^4%p==1 o4 = (true, false, false) o4 : Sequence i5 : (p,r) = getPrimeWithRootOfUnity(12,11,Range=>(100,200)) o5 = (157, 22) o5 : Sequence i6 : factor(r^n-1) 2 2 o6 = 3 5*7*13 23*97*157*463*1489 o6 : Expression of class Product i7 : r^12%p==1, r^6%p==1, r^4%p==1 o7 = (true, false, false) o7 : Sequence

## See also

• nextPrime -- compute the smallest prime greater than or equal to a given number
• Range -- can be assigned a integral interval

## Ways to use getPrimeWithRootOfUnity :

• "getPrimeWithRootOfUnity(ZZ,ZZ)"

## For the programmer

The object getPrimeWithRootOfUnity is .