mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Abstract Algebra & Algebraic Number Theory

Reply
 
Thread Tools
Old 2017-11-04, 16:14   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·79 Posts
Post Solving for x in Phi(n, x) = 0 (mod p)

Is there an algorithm, for any number p satisfying the conditions that each prime factor q of p is 1 (mod n), to solve for x > 1 such that Phi(n, x) = 0 (mod p), where Phi(n, x) is the nth cyclotomic polynomial.

One method I know for prime p only is suppose we want to solve for x > 1, Phi(n, x) = 0 (mod p). n must divide phi(p) = p-1, so using (p-1)/n as the exponent, take any base b and solve x = b^((p-1)/n) (mod p). x will be a solution to Phi(n, x) = 0 (mod p).

For example, take n = 5, and p = 11.

Solve for Phi(x, 5) = 0 (mod 11), or more simply x^4+x^3+x^2+x+1 = 0 (mod 11).

We can do this by setting r = phi(11)/5 = 10/5 = 2 and choosing any b value, say b = 3.

Compute x = b^r (mod 11) = 3^2 (mod 11) = 9 (mod 11). Since we get x = 9, 9 is a solution to x^4+x^3+x^2+x+1 = 0 (mod 11), as 9^4+9^3+9^2+9+1 = 7381, is a multiple of 11.

Now suppose we are solving for Phi(x, 5) = 0 (mod 31*11^2), or more simply x^4+x^3+x^2+x+1 = 0 (mod 3751).

This method does not seem to work since, r is set to phi(3751)/5 = 660, and x = b^660 (mod 3751) is always 1 (mod 3751) if gcd(b, 3751) = 1.

A possible, but slow approach is to solve for x^4+x^3+x^2+x+1 = 0 (mod 121) first, and set r to phi(121)/5 = 22, and choose b = 2.

2^22 (mod 121) = 81, and 81^4+81^3+81^2+81+1 is a solution. (If you were to work with small numbers, you could've found that 121 = 3^4+3^3+3^2+3+1, x = 3 is also a solution, as well as x = 9 and x = 27.

The problem is that

Phi(5, 3) = 25 (mod 31)
Phi(5, 9) = 24 (mod 31)
Phi(5, 27) = 29 (mod 31)
Phi(5, 81) = 4 (mod 31)

Since all of these can be written in base 3 form, i.e. 3^(5*x), and by Fermat's Little Theorem, b^(p-1) = 1 (mod p) if p is prime and gcd(b, p) = 1. So we can also determine that 3 is a primitive root modulo 31, and the multiplicative order of 3 modulo 31 is 30. Therefore 3^30 = 1 (mod 31), 3^30-1 = 1 (mod 31), 3^(6*5) = 1 (mod 31), Phi(5, 3^6) = 0 (mod 31), since 3^6 is not 1 (mod 31). Also recall that since Phi(5, 3) is divisible by 11^2, Phi(5, 3^n) will be divisible by 11^2, hence Phi(5, 3^6) = 0 (mod 3751). Notice this could've not been done by doing the "lazy base" method described above, since there is no solution to b^660 = 729 (mod 3751). However, any attempt at finding a solution to x^22 (mod 121) is successful since x = 3 (one of the solutions), can be obtained since there exist solutions to b^22 = 3 (mod 121), b = 5, 6, hence 5^22 = 6^22 = 3 (mod 121).

For any such p^k*q where p and q are primes congruent to 1 (mod n), is it possible to find one solution for each in Phi(n, a) = 0 (mod p^k), and Phi(n, b) = 0 (mod q) and combine them by applying the Chinese Remainder theorem to x = a (mod p^k), and x = b (mod q) for any such numbers k, and n?

What about if a prime p = 1 (mod n) is raised to some extremely large power k, and or multiplied by another prime q = 1 (mod n), then is it significantly easy to solve for x > 1, Phi(n, x) = 0 (mod q*p^k)? Do the methods described above still work?

Last fiddled with by carpetpool on 2017-11-04 at 16:24
carpetpool is offline   Reply With Quote
Old 2017-11-04, 16:53   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

3·5·97 Posts
Default

The following section from our Number Theory discussion group may be useful:
http://www.mersenneforum.org/showthread.php?t=21949
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Solving systems of equations modulo n carpetpool carpetpool 2 2017-02-05 20:40
Solving x^2 + x + 1 == 0 (mod mp) paulunderwood Miscellaneous Math 17 2016-12-31 22:11
Solving x^2==1 (mod n) paulunderwood Miscellaneous Math 2 2016-12-30 07:34
New Method for Solving Linear Systems Dubslow Miscellaneous Math 24 2012-08-24 10:46
solving modular constraints Joshua2 Homework Help 12 2010-02-19 22:59

All times are UTC. The time now is 10:31.

Sat Oct 31 10:31:26 UTC 2020 up 51 days, 7:42, 2 users, load averages: 1.74, 1.77, 1.86

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.