# Number Theorynumber theory

##### Member
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
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
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
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.