• Support PF! Buy your school textbooks, materials and every day products Here!

Applying Chinese Remainder Theorem to polynomials

  • Thread starter stgermaine
  • Start date
  • #1
48
0

Homework Statement


Find all integers x such that
[itex] 7x \equiv 11 mod 30 [/itex] and
[itex] 9x \equiv 17 mod 25 [/itex]


Homework Equations


I guess the Chinese Remainder theorem and Bezout's theorem would be used here.



The Attempt at a Solution


I can do this if the x-terms didn't have a coefficient. I'd just rewrite the congruences so that x - 11 = 30k etc and use Euclid's algorithm to solve it, which is not too difficult.
I'm just confused as to what to do since there are the coefficients and I'm not too sure what to do.

Thanks
 

Answers and Replies

  • #2
Curious3141
Homework Helper
2,843
87

Homework Statement


Find all integers x such that
[itex] 7x \equiv 11 mod 30 [/itex] and
[itex] 9x \equiv 17 mod 25 [/itex]


Homework Equations


I guess the Chinese Remainder theorem and Bezout's theorem would be used here.



The Attempt at a Solution


I can do this if the x-terms didn't have a coefficient. I'd just rewrite the congruences so that x - 11 = 30k etc and use Euclid's algorithm to solve it, which is not too difficult.
I'm just confused as to what to do since there are the coefficients and I'm not too sure what to do.

Thanks
The first step is to get rid of those coefficients by computing their respective modular multiplicative inverses.

So the system becomes ##x \equiv 7^{-1}.11 \pmod {30}## and ##x \equiv 9^{-1}.17 \pmod {25}##.

You can do this because the coefficients are relatively prime to those moduli.

Do you know how to compute those inverses? If not, you can read: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse and http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm (for the actual algorithm). A quick calculator is available online at: http://www.cs.princeton.edu/~dsri/modular-inversion.html [Broken]
 
Last edited by a moderator:

Related Threads on Applying Chinese Remainder Theorem to polynomials

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
0
Views
977
Replies
2
Views
499
Replies
0
Views
2K
Replies
0
Views
3K
Replies
1
Views
534
Replies
1
Views
1K
Top