Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Simultaneous Modulus Congruencies


Date: 04/18/2001 at 03:11:48
From: Ooi Chin Wah
Subject: Number theory

Thanks for your answers to the questions that I asked earlier. I would 
be very grateful if you can help me again.

Solve x = 3 (mod 8), x = 11 (mod 20) and x = 1 (mod 15).

Thanks.


Date: 04/18/2001 at 10:01:54
From: Doctor Rob
Subject: Re: Number theory

Thanks for writing back to Ask Dr. Math.

This is equivalent to solving the following congruencies with 
prime-power moduli:

     x = 3 (mod 8)
     x = 11 = 3 (mod 4)
     x = 11 = 1 (mod 5)
     x = 1 (mod 3)
     x = 1 (mod 5)

Notice that the second and fifth congruencies are redundant, so you 
are reduced to solving:

     x = 3 (mod 8)
     x = 1 (mod 3)
     x = 1 (mod 5)

The last two are easily combined to get:

     x = 3 (mod 8)
     x = 1 (mod 15)

Now use the fact that:

     2*8 + (-1)*15 = 1

to conclude that:

     15^(-1) = -1 = 7 (mod 8)
     8^(-1)  = 2 (mod 15)

Now you are ready to use the Chinese Remainder Theorem. I leave the 
rest to you.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/