PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] conditional congruences (Topic)

Consider congruences of the form

$\displaystyle f(x) \;:=\; a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0 \;\equiv\; 0 \pmod{m}$ (1)

where the coefficients $a_i$ and $m$ are rational integers. Solving the congruence means finding all the integer values of $x$ which satisfy (1).
  • If $a_i \equiv 0 \pmod{m}$ for all $i$ 's, the congruence is satisfied by each integer, in which case the congruence is identical (cf. the formal congruence). Therefore one can assume that at least $$a_n \not\equiv 0 \pmod{m},$$ since one would otherwise have $a_nx^n \equiv 0 \pmod{m}$ and the first term could be left out of (1). Now, we say that the degree of the congruence (1) is $n$ .
  • If $x = x_0$ is a solution of (1) and $x_1 \equiv x_0 \pmod{m}$ , then by the properties of congruences, $$f(x_1) \;\equiv\; f(x_0) \;\equiv\; 0 \pmod{m},$$ and thus also $x = x_1$ is a solution. Therefore, one regards as different roots of a congruence modulo $m$ only such values of $x$ which are incongruent modulo $m$ .
  • One can think that the congruence (1) has as many roots as is found in a complete residue system modulo $m$ .




"conditional congruences" is owned by pahio.
(view preamble | get metadata)

View style:

See Also: linear congruence, quadratic congruence

Also defines:  degree of congruence, root of congruence, root

This object's parent.

Attachments:
linear congruence (Definition) by Mathprof
quadratic congruence (Theorem) by pahio
congruence of arbitrary degree (Theorem) by pahio
Log in to rate this entry.
(view current ratings)

Cross-references: complete residue system, properties, degree, term, formal congruence, congruence, rational integers, coefficients
There are 48 references to this entry.

This is version 3 of conditional congruences, born on 2009-03-27, modified 2009-05-16.
Object id is 11720, canonical name is ConditionalCongruences.
Accessed 937 times total.

Classification:
AMS MSC11A05 (Number theory :: Elementary number theory :: Multiplicative structure; Euclidean algorithm; greatest common divisors)
 11A07 (Number theory :: Elementary number theory :: Congruences; primitive roots; residue systems)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

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