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

[Suvadip]

Find the least positive integer x such that x=5 (mod 7), x=7 (mod 11) and x=3(mod 13).

How to proceed?

 

[Amer]

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

 

[ThePerfectHacker]

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.

 

[HallsofIvy]

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.

 

[chisigma]

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$