mersenneforum.org Solving for x in Phi(n, x) = 0 (mod p)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-11-04, 16:14 #1 carpetpool     "Sam" Nov 2016 22·79 Posts 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
 2017-11-04, 16:53 #2 Nick     Dec 2012 The Netherlands 3·5·97 Posts The following section from our Number Theory discussion group may be useful: http://www.mersenneforum.org/showthread.php?t=21949

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 2 2017-02-05 20:40 paulunderwood Miscellaneous Math 17 2016-12-31 22:11 paulunderwood Miscellaneous Math 2 2016-12-30 07:34 Dubslow Miscellaneous Math 24 2012-08-24 10:46 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.