2017-11-04, 16:14 | #1 |
"Sam"
Nov 2016
2^{2}·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 |
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 |
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 |