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 => a sequence, 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

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