Find all integers $x$ such that $x ≡ 5 (\mod 8)$ and $x ≡ 73 (\mod 81)$.
Should I think like this:
$x = 5 + 8a$
$5 +8a = 73 + 81a → 68 = 72a$
After that I'm stuck.
Asked
Active
Viewed 133 times
2
-
2Have you ever heard about Chinese Remainder Theorem? This is exactly what you need to solve your problem. – Crostul Oct 28 '16 at 20:52
-
Do you agree with the new title I suggest ? In particular, the word "mathematics" doesn't bring any information : it is a mathematics' site! – Jean Marie Oct 28 '16 at 21:09
1 Answers
3
Let's call that integer $n$ instead of $x$. We have some $x\in\Bbb{Z}$ such that: $$n=8x+5$$ and another $y\in\Bbb{Z}$ such that: $$n=81y+73$$ putting this together yields: $$8x+5=81y+73$$ $$8x-81y=68$$ We now use the extended euclidean algorithm to obtain: $$(x,y)=(-680+81k,-68-8k)$$ Which gives: $$n=8x+5=8(-680+81k)+5=-5440+648k+5=648k-5435$$ for all $k\in\Bbb{Z}$. Note you can also use $n=648k+397$, as $-5435\equiv397\pmod{648}$
Mastrem
- 8,331
-
No problem. By the way, if you think this answer was helpful you can upvote if you want ;) – Mastrem Oct 28 '16 at 21:14
-
-