PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (192)
Orphanage
Unclass'd
Unproven (496)
Corrections (20)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] polynomial congruence (Definition)

Let $ m$ be a positive integer. Two polynomials $ f(X_1,\,X_2,\,\ldots,\,X_n)$ and $ g(X_1,\,X_2,\,\ldots,\,X_n)$ with integer coefficients are said to be polynomial congruent modulo $ m$, denoted

$\displaystyle f(X_1,\,X_2,\,\ldots,\,X_n)\,\,\overline{\equiv}\,\,g(X_1,\,X_2,\,\ldots,\,X_n) \pmod{m},$
iff all coefficients of the difference polynomial $ f-g$ are divisible by $ m$.

The polynomial congruence is an equivalence relation in the set $ \mathbb{Z}[X_1,\,X_2,\,\ldots,\,X_n]$.

Examples

  1. $ (X\!+\!Y)^p \,\,\, \overline{\equiv} \,\, X^p\!+\!Y^p \pmod{p}$ when $ p$ is a positive prime number. This result is easily proved with the binomial theorem (cp. the freshman's dream) and may be by induction generalized to
    $\displaystyle (X_1\!+\!X_2\!+\ldots+\!X_n)^p \,\,\, \overline{\equiv} \,\, X_1^p\!+\!X_2^p\!+\ldots+\!X_n^p \pmod{p}.$
    If one substitutes in this congruence 1 for all $ X_1$, $ X_2$, ..., $ X_n$, one obtains the congruence
    $\displaystyle n^p \equiv n \pmod p;$
    similar substitution of $ -1$ shows that the last congruence is valid also for negative integers $ n$. If it is supposed that $ p$ is not factor of $ n$, we have got the Fermat's little theorem.
  2. Let $ p$ be a positive prime number. It is possible that the $ n^\mathrm{th}$ degree congruence
    $\displaystyle P(x) := a_0x^n\!+\!a_1x^{n-1}\!+\ldots+\!a_n \equiv 0 \pmod{p},$
    where $ a_i \in \mathbb{Z} \,\, \forall i$ and $ p \nmid a_0$, has $ n$ modulo $ p$ incongruent roots $ x = x_1,\,x_2,\,\ldots,\,x_n$. We then have the polynomial congruence
    $\displaystyle P(x) \,\, \overline{\equiv} \,\, a_0(x\!-\!x_1)(x\!-\!x_2)\cdots(x\!-\!x_n) \pmod{p}.$
    Especially, we have
    $\displaystyle x^{p-1}\!-\!1 \,\,\overline{\equiv}\,\, (x\!-\!1)(x\!-\!2)\cdots(x\!-\!p\!+\!1) \pmod{p}, $
    because Fermat's little theorem guarantees the roots $ x = 1,\,2,\,\ldots,\,p\!-\!1$ for the congruence $ x^{p-1}\!-\!1 \equiv 0 \pmod{p}$. If the value $ x = 0$ is substituted in the previous polynomial congruence, it gives
    $\displaystyle -1 \equiv (-1)^{p-1}(p\!-\!1)! \pmod{p}$
    or
    $\displaystyle (p\!-\!1)! \equiv -1 \pmod{p},$
    which is half of Wilson's theorem. The reverse part of this theorem follows from the last congruence so that if $ p$ were not prime, then the number $ -1$ would be divisible by any proper divisor of $ p$.



"polynomial congruence" is owned by pahio.
(view preamble)

View style:

See Also: congruence relation on an algebraic system, a polynomial of degree $n$ over a field has at most $n$ roots, ideal decomposition in Dedekind domain, example of gcd, Fermat's little theorem, Wilson's theorem, freshman's dream, using primitive roots and index to solve congruences

Other names:  formal congruence

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: proper divisor, number, Wilson's theorem, roots, degree, Fermat's little theorem, factor, negative, induction, freshman's dream, binomial theorem, prime number, equivalence relation, divisible, difference, iff, congruent, coefficients, polynomials, integer, positive
There are 3 references to this entry.

This is version 23 of polynomial congruence, born on 2004-06-06, modified 2008-08-12.
Object id is 5894, canonical name is PolynomialCongruence.
Accessed 4580 times total.

Classification:
AMS MSC: 11A07 (Number theory :: Elementary number theory :: Congruences; primitive roots; residue systems)
 11C08 (Number theory :: Polynomials and matrices :: Polynomials)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)