has a quotient x3 + 2x2 + 6x + 20 and a remainder 60.
Theorem For and
an integer b, we can write f(x) = (x - b)g(x)+c
where g is a polynomial with degree g = degree f - 1 and c is an integer.
Proof. By induction on the degree of f. The result
is clearly true when the degree
of f is zero. Suppose that the assertion holds when the degree of f is less than
now take Now the nth degree coefficient of f
is an which
is the same as the nth degree coefficient of
has degree less than n. By induction,
where the degree of is less than n. Then
By induction, the result holds for all polynomials f.
Definition. The polynomials
congruent as polynomials modulo m (written f ≡ g (poly modm)) if
for each j with 0 ≤ j ≤ m. Another way of saying this is f(x) - g(x) = mh(x)
h is a polynomial with integer coefficients.
Example. x2 + x - 12 ≡ x2 + x + 2 (poly mod 7).
However, although by Fermat’s
theorem we have x7 ≡ x (mod 7) for every x, we do not have x7 ≡ x(poly mod 7).
Definition. For f as above, the degree of f modulo
m is the largest j such that
If f is congruent to zero modulo m then the degree is undefined.
(poly mod m) and
(poly modm) then
(poly mod m)
(poly mod m). Also
(poly mod n) as was noted by a
member of the audience. If m = p is prime then the degree of fg modulo p is the
degree of f modulo p plus the degree of g modulo p.
Theorem. Let p be prime and let f(x) be a
polynomial which is not congruent to
zero as a polynomial modulo p.
(a). There exist integers
and a polynomial g(x), such that g has no roots
modulo p and
Proof of the Theorem. (a). We prove this by
induction on the degree of f. Suppose
it holds when the degree of f is less than n, and now take f whose degree is
n. If f has no root modulo p then we can take g = f and no rs. If f has a root r
modulo p. Then by long division we can write
where the degree of
is n - 1. Then plugging in x = r we get
0 ≡ f(r) ≡ c (mod p)
By applying the inductive hypothesis to
we get (*) for f. By induction we are done.
are roots of f modulo p and if a is not one of the
g(a) (mod p)
which is a product of non -zero elements modulo p and hence
non-zero modulo p. This
shows that the roots modulo p are precisely
Start solving your Algebra Problems
in next 5 minutes!
Download (and optional CD)
Click to Buy Now:
2Checkout.com is an authorized reseller
of goods provided by Sofmath
Attention: We are
currently running a special promotional offer
for Algebra-Answer.com visitors -- if you order
Algebra Helper by midnight of
you will pay only $39.99
instead of our regular price of $74.99 -- this is $35 in
savings ! In order to take advantage of this
offer, you need to order by clicking on one of
the buttons on the left, not through our regular
If you order now you will also receive 30 minute live session from tutor.com for a 1$!
You Will Learn Algebra Better - Guaranteed!
Just take a look how incredibly simple Algebra Helper is:
: Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:
Step 2 :
Let Algebra Helper solve it:
Step 3 : Ask for an explanation for the steps you don't understand:
Algebra Helper can solve problems in all the following areas:
simplification of algebraic expressions (operations
with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots
(radicals), absolute values)