The Chinese Remainder Theorem (the CRT)

Click For Summary

Discussion Overview

The discussion revolves around finding the lowest number that meets specific remainder conditions when divided by a series of integers. It explores the application of the Chinese Remainder Theorem (CRT) and hints at a quicker method for this particular case.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • One participant presents a problem involving finding a number with specific remainders when divided by integers 2 through 6.
  • Another participant suggests that the answer is 59.
  • A later reply confirms that 59 is indeed the correct answer and explains that it can be derived by multiplying the divisors and subtracting one, while noting that smaller numbers also satisfy the conditions.
  • Further discussion introduces the Euclidean algorithm as a method related to the CRT, although one participant expresses uncertainty about the details of this relationship.
  • Participants express appreciation for the explanations provided, indicating that they find the solutions useful.

Areas of Agreement / Disagreement

There is agreement on the answer being 59, but participants acknowledge that there may be smaller numbers that also satisfy the conditions. The relationship between the problem and the CRT is discussed, but details remain unclear for some participants.

Contextual Notes

Some assumptions about the methods used to derive the answer are not fully explored, and there is a lack of clarity regarding the application of the Euclidean algorithm in this context.

Who May Find This Useful

Readers interested in mathematical problem-solving, particularly those studying number theory or the Chinese Remainder Theorem, may find this discussion beneficial.

DeaconJohn
Messages
122
Reaction score
0
Find the lowest number that has a remainder of
1 when divided by 2,
2 when divided by 3,
3 when divided by 4,
4 when divided by 5, and
5 when divided by 6.

It is possible to solve this by applying the general algorithm that solves Chinese Remainder problems. But, for this special case of the CRT, there is an much quicker way. You just have to look at it right and the answer pops out. ...

Naturally, the point of this problem is more about finding the trick than it is about finding the right answer.

Hints:
6=3x2 and 4 = 2x2.
Problem Source:
Problem 35 on p. 11 in Chp. 1 of Carter and Russell, "The Complete Book of Fun Maths"
 
Mathematics news on Phys.org
Is it 59?
 
daskalou said:
Is it 59?

Yes!

Solution Explained:

If you multiply all the numbers in the right hand column together and subtract one, you get a number that satisfies all the conditions, except there are smaller numbers that work too.

The least common multiple minus one is the smallest number that works. And that is 59.

Relationship with the Chinese Remainder Theorem spelled out:

To solve the problem using the usual proof of the CRT, one applies the Eucledian algorithm. The Eucledian algorithm is often first introduced as a method of computing the gcd, and, given the gcd, one can easily compute the lcd. [I forget how this last demonstration goes. If someone could remind me, that would be great.]

Hence this problem presents the CRT as a generalization of the computation of the gcd using the Eucledian algorithm.
 
Last edited:
Solution:

Ah, I've seen this trick before. Denote the number we're looking for as x and view the problem in terms of congruencies and it should be evident what happens when you add 1 to x. Then find the lcm of the product of the divisors in the problem. Count 2, 3, another 2 (for 4), 5, and 6 is covered. So x+1 = 2*2*3*5 => x = 59.
 
snipez90 said:
Solution:

Ah, I've seen this trick before. Denote the number we're looking for as x and view the problem in terms of congruencies and it should be evident what happens when you add 1 to x. Then find the lcm of the product of the divisors in the problem. Count 2, 3, another 2 (for 4), 5, and 6 is covered. So x+1 = 2*2*3*5 => x = 59.

Snipez90,

All I can say is "Excellent." Really, a nice explanation.

DJ
 
thx very much. Your soln is very useful
 

Similar threads

MHB How to solve Chinese Remainder Theorem
  • · Replies 11 ·
Replies
11
Views
3K
MHB What is the remainder when m+n is divided by 1000 in a trigonometric challenge?
  • · Replies 2 ·
Replies
2
Views
1K
MHB Divisibility of (1!+2!+3!+...+100!)^2 by 5
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Remainders, need Help proving a simple notion
  • · Replies 3 ·
Replies
3
Views
1K
Why Does Expanding (13-8)^99 Not Yield the Same Remainder as 5^99 Modulo 13?
  • · Replies 7 ·
Replies
7
Views
2K
High School Finding the remainder of an algebraic quotient
  • · Replies 4 ·
Replies
4
Views
1K
Finding Integer with Chinese Remainder Theorem
  • · Replies 3 ·
Replies
3
Views
2K
A tricky remainder theorem problem
  • · Replies 15 ·
Replies
15
Views
3K
Problem with a product of 2 remainders (polynomials)
  • · Replies 4 ·
Replies
4
Views
2K
Long Division and Remainder Theorem
  • · Replies 5 ·
Replies
5
Views
2K