- Thread starter
- #1

- Thread starter suvadip
- Start date

- Thread starter
- #1

$ x = 5 (mod 7) $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 = 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

- Jan 26, 2012

- 236

If $x \equiv a ~ (n)$ and $x\equiv b ~ (m)$ where $n,m$ are relatively prime positive integers then $x\equiv ab ~ (nm)$.Find the least positive integer x such that x=5 (mod 7), x=7 (mod 11) and x=3(mod 13).

How to proceed?

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.

- Jan 29, 2012

- 1,151

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.

- Feb 13, 2012

- 1,704

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...Find the least positive integer x such that x=5 (mod 7), x=7 (mod 11) and x=3(mod 13).

How to proceed?

http://mathhelpboards.com/number-theory-27/applications-diophantine-equations-6029.html#post28283

Kind regards

$\chi$ $\sigma$