Difference between revisions of "Polynomial congruences"
m (→See Also) |
(→Solving) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
<cmath>f(x) \equiv 0 \pmod {m}</cmath> | <cmath>f(x) \equiv 0 \pmod {m}</cmath> | ||
| − | where <math>f(x)</math> is an [[arithmetic function]] whose range is the integers and <math>m</math> is an integer. | + | where <math>f(x)</math> is an [[arithmetic function]] and a [[polynomial]] whose range is the integers and <math>m</math> is an integer. |
| − | + | ==Solving== | |
| + | There are a few ways of solving polynomial congruences, and special cases can make it easier. | ||
| + | |||
| + | ===Introductary=== | ||
| + | |||
| + | Some polynomial congruences can be solved obviously. For example, the congruence | ||
| + | |||
| + | <cmath>16x^2 \equiv 13 \pmod {192}</cmath> | ||
| + | |||
| + | obviously have no solution, since <math>\gcd (16,192)</math> don't divide <math>13</math>. | ||
| + | |||
| + | Additionally, if <math>f(x)</math> is of special forms, the congruence can be solve rather easily. | ||
| + | |||
| + | ===Intermediate=== | ||
| + | |||
| + | There are two intermediate level ways of solving polynomial congruences. | ||
| + | |||
| + | First, we can apply [[Hensel's Lemma]] repeatedly to solve the congruence modulo prime powers, and then using then [[Chinese Remainder Theorem]] we can obtain the solution modulo <math>n</math>. More information can be found on that page. | ||
| + | |||
| + | Secondly, you can use the [[index]] of an integer, a relatively more advanced method using [[Primitive roots]] and the [[Order of a integer]]. We take the index of both sides of the congruence, and obtain a much easier congruence regarding the index of the variable. Then we can use that to find the variable itself. More information can be found [[index|here]]. | ||
| + | |||
| + | ===Olympiad=== | ||
| + | |||
| + | ''This section currently have no content. Please add an olympiad way of solving polynomial congruences if you can. '' | ||
==See Also== | ==See Also== | ||
| Line 12: | Line 35: | ||
{{stub}} | {{stub}} | ||
| − | [[Category: | + | [[Category:Definitions]] |
Latest revision as of 20:17, 19 January 2025
Polynomial Congruences are congruences in the form
![\[f(x) \equiv 0 \pmod {m}\]](http://latex.artofproblemsolving.com/1/5/5/155003e2c4a7d9491adc7609f91ef131b648b195.png)
where 
is an arithmetic function and a polynomial whose range is the integers and 
is an integer.
Solving
There are a few ways of solving polynomial congruences, and special cases can make it easier.
Introductary
Some polynomial congruences can be solved obviously. For example, the congruence
![\[16x^2 \equiv 13 \pmod {192}\]](http://latex.artofproblemsolving.com/e/b/2/eb21d4a93c8dfc290384215a59276c7fe1a4435b.png)
obviously have no solution, since 
don't divide 
.
Additionally, if is of special forms, the congruence can be solve rather easily.
Intermediate
There are two intermediate level ways of solving polynomial congruences.
First, we can apply Hensel's Lemma repeatedly to solve the congruence modulo prime powers, and then using then Chinese Remainder Theorem we can obtain the solution modulo 
. More information can be found on that page.
Secondly, you can use the index of an integer, a relatively more advanced method using Primitive roots and the Order of a integer. We take the index of both sides of the congruence, and obtain a much easier congruence regarding the index of the variable. Then we can use that to find the variable itself. More information can be found here.
Olympiad
This section currently have no content. Please add an olympiad way of solving polynomial congruences if you can.
See Also
This article is a stub. Help us out by expanding it.
