Polynomial congruences

Polynomial Congruences are congruences in the form

$f(x) \equiv 0 \pmod {m}$

where $f(x)$ is an arithmetic function and a polynomial whose range is the integers and $m$ 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}$

obviously have no solution, since $\gcd (16,192)$ don't divide $13$ .

Additionally, if $f(x)$ 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 $n$ . 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.

Page

Toolbox

Search

Polynomial congruences

Contents

Solving

Introductary

Intermediate

Olympiad

See Also