MHB What Is the Least Positive Integer x Satisfying These Congruences?

AI Thread Summary
The discussion focuses on finding the least positive integer x that satisfies the congruences x=5 (mod 7), x=7 (mod 11), and x=3 (mod 13). Participants outline methods using the Chinese Remainder Theorem and modular arithmetic to derive the solution. Key steps include expressing x in terms of k and j, solving simultaneous congruences, and verifying the final result. The least positive integer found through calculations is 887, which meets all specified conditions. The problem is noted for its historical significance in illustrating ancient Chinese military strategies.
Suvadip
Messages
68
Reaction score
0
Find the least positive integer x such that x=5 (mod 7), x=7 (mod 11) and x=3(mod 13).

How to proceed?
 
Mathematics news on Phys.org
suvadip said:
Find the least positive integer x such that x=5 (mod 7), x=7 (mod 11) and x=3(mod 13).

How to proceed?

$ x = 5 (mod 7) $
$ x = 7k +5 $ for some k
Sub in the second
$7k+5 = 7 (mod 11) $
$7k = 2 (mod 11) $ the multiplication inverse of 7 in $\mathbb{Z}_{11}$
$7(3) = -1 (mod 11) \Rightarrow 7(7)(9) = 1 (mod 11) \Rightarrow 7(8) = 1 (mod 11)$ so

$8(7k) = 16 (mod 11) \Rightarrow k = 5 (mod 11)$
$ k = 11t + 5 $
So $ x = 7(11t+5) + 5 = 77t + 40...(*) $
Now the last equation
$ 77t + 40 = 3 (mod 13)$ , solve it for t it will be something like t = 13m + c sub it in (*)
Chinese remainder theorem - Wikipedia, the free encyclopedia
 
suvadip said:
Find the least positive integer x such that x=5 (mod 7), x=7 (mod 11) and x=3(mod 13).

How to proceed?

If $x \equiv a ~ (n)$ and $x\equiv b ~ (m)$ where $n,m$ are relatively prime positive integers then $x\equiv ab ~ (nm)$.

Since $x\equiv 5 ~ (7)$ it means $x\equiv 5 + 7k ~ (7)$.
Since $x\equiv 7 ~ (11)$ it means $x\equiv 7 + 11j ~ (11)$.

Now find integers $k,j$ so that $5 + 7k = 7 + 11j$. We require $11j - 7k = -2$. For example, choose $j=-4$ and $k=-6$. This tells us that $x\equiv -37 ~ (7)$ and $x\equiv -37 ~ (11)$, now since $7,11$ are relatively prime we get $x\equiv -37~ (77)$.

Continue from here.
 
Equivalently: if x=5 (mod 7), x=7 (mod 11) and x=3(mod 13),
then from x= 3 (mod 13) (it is not necessary to start with the largest "modulus" but it makes the calculations easier) x= 3+ 13i for some integer I.

Then x= 3+ 13i= 7 (mod 11) so 3+ 2i= 7 (mod 11), 2i= 4 (mod 11), i= 2 (mod 11).
That means that i= 2+ 11j for some integer j so x= 3+ 13i= 3+ 13(2+ 11j)= 29+ 143j.

Then x= 29+ 143j= 5 (mod 7) so 1+ 3j= 5 (mod 7), 3j= 4 (mod 7). 3(6)= 18= 14+ 4. That means that j= 6+ 7k for some integer k and x= 29+ 143j= 29+ 143(6+ 7k)= 887+ 1001k.

Check: 887/7= 126 with remainder 5. 887/11= 80 with remainder 7. 887/13= 68 with remainder 3.
 
suvadip said:
Find the least positive integer x such that x=5 (mod 7), x=7 (mod 11) and x=3(mod 13).

How to proceed?

This problem is of historical importance because it illustrates the method used by the chinese generals in the Middle Age to know the number of soldiers in a battalion. The general solution of this problem is illustrated in... http://mathhelpboards.com/number-theory-27/applications-diophantine-equations-6029.html#post28283

Kind regards

$\chi$ $\sigma$
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top