Oops, I sort of forgot this was here.

by t0rajir0u, Dec 27, 2006, 8:51 AM

Let's get right into the heart of a new topic that I don't see addressed very often.

Lots of people have experience with using modular arithmetic on positive integers. That's all fine and dandy. The basis of modular arithmetic on the positive integers is the existence of the division algorithm, which says that given two positive integers $a, b$, there exist integers $q$ and $r$ such that

$a = bq+r, 0 \le r < b$

We then say that $r$ is the remainder upon dividing $a$ by $b$. We also say that if two integers $x, y$ have the same remainder upon division by $m$, then $x \equiv y \bmod m$.

Hmm. Where else have you seen a division algorithm?

That's right. Polynomials! (We'll restrict this discussion to polynomials with integer coefficients, which have neat-o number theoretic properties.)

If you've never seen the polynomial division algorithm before, it states that given two polynomials $A(x), B(x)$, there exist polynomials $Q(x)$ and $R(x)$ such that

$A(x) = B(x) Q(x)+R(x)$

Where either $R(x) = 0$ or $\text{deg }R(x) < \text{deg }B(x)$.

We can therefore define the analogous tool of polynomial modular arithmetic, which is an extremely concise way to attack a lot of polynomial problems, and also produces some interesting isomorphisms which I may or may not get to...



Basically, we say of two polynomials $f(x), g(x)$ that $f(x) \equiv g(x) \bmod m(x)$ whenever $m(x) | \left( f(x)-g(x) \right)$, or equivalently if the two polynomials leave the same remainder upon division by $m(x)$.

Because we can use familiar techniques from integer modular arithmetic, we can trivialize a lot of those "find the remainder" type problems.

Example: Find the remainder when $x^{81}+x^{49}+x^{25}+x^{9}+x$ is divided by $x^{3}-x$.

I've been seeing this problem a lot lately. Most people tackle it in the nitty-gritty using the division algorithm, but why bother? Take it $\bmod (x^{3}-x)$.



At this point, you might realize that all integer polynomials will now fall into "polynomial residue classes." You might also realize that these residue classes can be characterized by quadratic polynomials (since if there are cubic terms or higher we can just reduce them.) Finally, you might realize that

$x^{2k+1}\equiv x \bmod (x^{3}-x)$
$x^{2k}\equiv x^{2}\bmod (x^{3}-x)$

And therefore that

$x^{81}+x^{49}+x^{25}+x^{9}+x \equiv x+x+x+x+x \equiv 5x \bmod (x^{3}-x)$

And we are done.



This opens up a fascinating line of questioning. If you're familiar with the ring-theoretic mathematics behind $\mathbb{Z}_{m}$, you might like to ask yourself about the properties of $\mathbb{Z}[x]_{m(x)}$. They're not that interesting until you decide to combine the two ideas and ask yourself about the properties of $\mathbb{Z}_{m}[x]_{M(x)}$.

Man, that's awesome! Ask yourself how many residue classes we have now. Or better yet, ask yourself how many of them are units. This stuff is pretty cool.

Again, for those of you familiar with the notation, ask yourself about $\mathbb{Z}[x]_{x^{2}+1}$. What does this ring remind you of?

Practice Problem 1: What is the remainder when $1+x+x^{2}+...+x^{2006}$ is divided by $1+x+x^{2}+...+x^{8}$?

Practice Problem 2: What is the remainder when $1+x+x^{2}+...+x^{2006}$ is divided by $x^{4}+x^{3}-x-1$?

Comment

10 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Interesting stuff. I learned a little. I wasn't aware it extended so well to polynomials.

by Pakman2012, Dec 27, 2006, 6:31 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ooo, nice stuff. :lol:

by 4everwise, Dec 28, 2006, 1:40 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
I see how it is. Don't like the way I solved it, huh? :wink:

1. Basically, we cancel out any eight terms with consecutive powers using your little mod trick, so we are just left with $1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}$, eh?

by paladin8, Dec 31, 2006, 8:58 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Is there a "simple" way to find residues in a certain mod? For example, it's pretty easy to check that $x^{2k+1}-x$ is divisible by $x^{3}-x$, but is there a simple way to generate this, especially for more complicated divisors?

by Phelpedo, Jan 1, 2007, 5:10 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Phelpedo wrote:
Is there a "simple" way to find residues in a certain mod? For example, it's pretty easy to check that $x^{2k+1}-x$ is divisible by $x^{3}-x$, but is there a simple way to generate this, especially for more complicated divisors?

Well certainly we can set $m(x) = 0$ (which is what happens in the polynomial residue) and see if you can play around. This is how I solve most remainder problems anyway.

Like for problem 2, we can factor $m(x) = (x^{3}-1)(x+1)$. Note that all the roots of $m(x)$ are the 6th roots of unity, so in this ring one must have $x^{6}=1$. Wow, plug that beast in, we're only left with a quintic, and you can do long division now JUST TWO TIMES!!!. Ooo, beat that.

by pkerichang, Jan 3, 2007, 4:02 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Phelpedo wrote:
Is there a "simple" way to find residues in a certain mod? For example, it's pretty easy to check that $x^{2k+1}-x$ is divisible by $x^{3}-x$, but is there a simple way to generate this, especially for more complicated divisors?

Yes :)

Recall that $\equiv$ is an equivalence relation. Among other things, this implies $a \equiv b \bmod m, c \equiv d \bmod m \implies ac \equiv bd \bmod m$.

Consider evaluating $\bmod (x^{2}-1)$, in which case

$x^{2k}\equiv \left( x^{2}\right)^{k}\equiv (1)^{k}\equiv 1$

And then consider $\bmod x$. Because $gcd(x, x^{2}-1) = 1$ (note that the Euclidean Algorithm holds with polynomials) we can use the Chinese Remainder Theorem (which also holds with polynomials) to conclude that $x^{2k}\equiv x^{2}, k \ge 1$ and $x^{2k+1}\equiv x, k \ge 0$.

:)

Alternately, an easier method: because

$x^{3}\equiv x \bmod (x^{3}-x)$

It follows that

$x^{3+k}\equiv x^{1+k}\bmod (x^{3}-x)$

Or, letting $n = 1+k$,

$x^{n+2}\equiv x^{n}\bmod (x^{3}-x)$

Inducting on this produces our result.




Edit: Jeffrey: Every nine terms. Oh snap.

Edit: pkerichang: Or we can use the congruence $x^{4}+x^{3}\equiv x+1$ to reduce to a cubic directly with no division. Oh snap.

by t0rajir0u, Jan 4, 2007, 5:04 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Darn. You fooled me with your $\ldots$.

by paladin8, Jan 6, 2007, 6:54 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
OK, so using this logic, how do we find the residue for $x^{5n}$ in $\mod (x^{2}+3x+2)$? (Random example)

by mysmartmouth, Jan 9, 2007, 4:43 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Hm you know you are touching on so much deep stuff here.
You will love it when you learn some algebra.

Everything you mention here is true because the polynomial ring is a Euclidean domain. Besides these nice extensions of modular arithmetic that hold in Euclidean domains, the deepest truths about them come in the consideration of modules.

A module over K[x] (K a field) is the same as a vector space over K together with a linear transformation (multiplication by x). A module over Z is equivalent to an abelian group (using additive notation). By proving a general structure theorem for modules over Euclidean Domains we can simultaneously knock out the classification of all abelain groups and the Canonical form for a linear transformation :)

by n^4 4, Jan 16, 2007, 2:58 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
I love how n^4 completely lost me with that speech. And I was understanding what was going on... beforehand.

Is there something wrong with doing number one this way?

$\frac{1+x+...+x^{2006}}{1+x+...+x^{8}}= \\ \frac{x^{2007}-1}{x^{9}-1}$

Which yields a remainder of 0...

by white_horse_king88, Jan 18, 2007, 3:27 AM

Various mathematical thoughts, ranging from problem-solving techniques to attempts to tie together related concepts.

avatar

t0rajir0u
Archives
- April 2009
New location!
A question about automata
+ March 2009
Some updates
+ February 2009
Fibonacci numbers @ HMMT
The combinatorics of basic calculus
A question and some thoughts II
+ January 2009
A question and some thoughts
Coefficients in the closed forms of linear recurrences
+ December 2008
The pretty picture post (crystals and cyclotomics)
Fun with Newton polynomials, Part III
+ November 2008
The Chinese Remainder Theorem and Lagrange Interpolation
+ October 2008
The magic of the Frobenius map
+ September 2008
Creative problem solving
A formal look at formal differentiation
+ August 2008
Transition
The title of this blog and enumerative combinatorics
Three approaches to sums of squares
+ July 2008
China Post 3: The Euclidean algorithm
China Post 2: The complex numbers
China Post 1: The problem of repeated roots
+ June 2008
Structure-preserving maps, Part II: Vector spaces
Fun with Newton Polynomials, Part II
Structure-preserving maps, Part I: Groups
+ May 2008
An "elementary" perspective on Dirichlet's theorem
Quadratic residues and cyclotomic polynomials
+ March 2008
Rational Solutions to Polynomials, Part II
Rational solutions to polynomials
+ January 2008
A generating functions approach to counting
+ December 2007
Fun with Newton polynomials
+ November 2007
A matrix derivation of Binet's formula
+ October 2007
A Digression
+ June 2007
A point to ponder
A topic from April
Post-ARML
Post-ARML
+ May 2007
A Quickie
+ April 2007
Algebra through geometry
From a college friend
From Gauss to Eisenstein
+ March 2007
It's been a long time...
+ February 2007
It's a New Day
More polynomials
Something Simple for a Change
+ January 2007
Back to Basics
Rings! Yay!
Intermezzo
+ December 2006
Oops, I sort of forgot this was here.
Complex identities
Shouts
Submit

  • orz $~~~~$

    by clarkculus, Jan 10, 2025, 4:13 PM

  • Insanely auraful

    by centslordm, Jan 1, 2025, 11:17 PM

  • Fly High :(

    by Siddharthmaybe, Oct 22, 2024, 8:34 PM

  • Dang it he is gone :(( /revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive.

    by 799786, Aug 4, 2022, 1:56 PM

  • annoying precision

    by centslordm, May 16, 2021, 7:34 PM

  • rip t0rajir0u

    by OlympusHero, Dec 5, 2020, 9:29 PM

  • Shoutbox bump xD

    by DuoDuoling0, Oct 4, 2020, 2:25 AM

  • dang hes gone :(

    by OlympusHero, Jul 28, 2020, 3:52 AM

  • First shout in July

    by smartguy888, Jul 20, 2020, 3:08 PM

  • https://artofproblemsolving.com/community/c2448

    has more.

    -πφ

    by piphi, Jun 12, 2020, 8:20 PM

  • wait hold up 310,000
    people visited this man?!?!??

    by srisainandan6, May 29, 2020, 5:16 PM

  • first shout in 2020

    by OlympusHero, Apr 4, 2020, 1:15 AM

  • in his latest post he says he moved to wordpress

    by MelonGirl, Nov 16, 2019, 2:43 AM

  • Please revive!

    by AopsUser101, Oct 30, 2019, 7:10 PM

  • first shout in october fj9odiais

    by bulbasaur., Oct 14, 2019, 1:14 AM

128 shouts
Tags
About Owner
  • Posts: 12167
  • Joined: Nov 20, 2005
Blog Stats
  • Blog created: Dec 5, 2006
  • Total entries: 48
  • Total visits: 321828
  • Total comments: 202
Search Blog
a