Welcome to our community

Be a part of something great, join today!

Number Theory number theory

suvadip

Member
Feb 21, 2013
69
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

Active member
Mar 1, 2012
275
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

Well-known member
Jan 26, 2012
236
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

Well-known member
MHB Math Helper
Jan 29, 2012
1,151
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

Well-known member
Feb 13, 2012
1,704