How can I effectively solve a system of congruences?

[bremenfallturm]

Homework Statement

Find all integers so that $x\equiv_8 5$ and $x\equiv_{81} 73$

Relevant Equations

$x=c\pmod{n} \equiv x=n\cdot k + c$ for an integer $k$

My attempt.

I think it might be that I solve the diophantine equation wrong, according to my anwer key it should be

I do not get a particular solution that is close to 397 as you can see.

 

[fresh_42]

You can solve it with https://www.dcode.fr/chinese-remainder or with the Chinese Remainder Theorem. You should proceed with the algorithm or as in the example mentioned there. The start is

$8$ and $81$ are coprime, so there are numbers $\alpha,\beta$ such that
$$
1=\alpha\cdot 8 + \beta \cdot 81
$$
by Bézout's lemma. $\alpha$ and $\beta$ are quite obvious in our case: $1=(-10)\cdot 8 + 1\cdot 81.$

Btw.: Here is explained how you write Formulas: https://www.physicsforums.com/help/latexhelp/
This would be better than pictures.

 

[PeroK]

Homework Statement: Find all integers so that $x\equiv_8 5$ and $x\equiv_{81} 73$
Relevant Equations: $x=c\pmod{n} \equiv x=n\cdot k + c$ for an integer $k$

My attempt.
View attachment 351441
View attachment 351442
I think it might be that I solve the diophantine equation wrong, according to my anwer key it should be

View attachment 351443
I do not get a particular solution that is close to 397 as you can see.

I just cranked it out from first principles. Just keep going from the point you gave up:
$$8k = 68 \ (mod \ 81) \implies 2k = 17 \ (mod \ 81) = 81m +17$$Where $m$ is odd etc.

 

[WWGD]

Isn't $397=49(8)+5$?
Have you seen the Chinese Remainder Theorem?

 

[bremenfallturm]

Chinese Remainder Theorem.

Have you seen the Chinese Remainder Theorem?

No, my lecturer explicitly said that it's not "part of the course". But looks like it's good to solve this assignment.

Btw.: Here is explained how you write Formulas: https://www.physicsforums.com/help/latexhelp/

If sorry if what I wrote was hard to read. I do know about formulas, in fact I'm a huge $\LaTeX$ fan. I exported my original solution but if hard to read I can consider rewriting all my solutions into TeX.

I realized I made a mistake when I wrote that $8k\equiv 68\pmod{81}$ is unsolveable with the inverse. In fact there exists an inverse and I got closer by using that instead:
(I hope that my handwritten notes are OK to post. If you can't read them please let me know and I'll rewrite them into TeX)

So now I found the correct value for $x$, but I don't understand where the $+648n$ part in the answer key comes from. Thankful for any help!

 

[PeroK]

I realized I made a mistake when I wrote that $8k\equiv 68\pmod{81}$ is unsolveable with the inverse.
So now I found the correct value for $x$, but I don't understand where the $+648n$ part in the answer key comes from. Thankful for any help!

I don't really understand the difficulty:
$$x \equiv 5 \ (mod \ 8) \Leftrightarrow x = 8k + 5$$$$x \equiv 73 \ (mod \ 81) \Leftrightarrow 8k + 5 = 81m + 73$$$$\Leftrightarrow 8k = 81m + 68$$The left-hand side is even, hence $m$ is even. Let $m = 2m_1$.
$$8k = 81(2m_1) + 68 \Leftrightarrow 4k = 81m_1 + 34$$And, again, $m_1 = 2m_2$ is even:
$$\Leftrightarrow 2k = 81m_2 + 17$$Now, $m_2$ must be odd ...

 

[fresh_42]

So now I found the correct value for x, but I don't understand where the +648n part in the answer key comes from.

$8$ and $81$ are coprime. So every $8\cdot 81=648$ numbers, you will get the same remainders for both of them. This means that $x$ can only be unique up to multiples of $648.$

 

[bremenfallturm]

I don't really understand the difficulty:

I think I'm having a hard time with this assignment because I:
(1) Have not learned about the Chinese root theorem
(2) Have not seen a similar assignment before
(3) Am very new to solving diophantine equations so
(4) I tend to approach solving them in one, very mechanical way:
1. Rewrite the equation $a\equiv b\pmod n\implies a=xn+bk\implies xn-bk=a$
2. Get a particular solution, either by directly seeing it or doing Euclidean algorithm in reverse
3. Given the particular solution $x_p$ we get $x=x_p+\frac{b}{gcd(n,b)}c, c\in \mathbb Z$

So when I encounter ways of solving diophantine equations that do not seem to do it in the way that I explained in (4), I get confused.

In your particular proposition, I do not see what insight I should get from that $m_2$ is odd.

$8$ and $81$ are coprime. So every $8\cdot 81=648$ numbers, you will get the same remainders for both of them. This means that $x$ can only be unique up to multiples of $648.$

This I understand intuitively now that you told me, but as I explained above (in (4)), I still approach diophantine equations in a very mechanical way. I would expect $648$ to be the result of $\frac{b}{gcd(n,b)}$ as in $x=x_p+\frac{b}{gcd(n,b)}c, c\in \mathbb Z$ (explained in (4.3) above). But I can't connect the fact that $648=8\cdot 81$ to my familar formulas (and I don't know where $b$ would come from in the first case), so I just have a hard time seeing the intuition behind the solution since I can't connect it to anything that I've worked with before.
If that makes any sense at all.

 

[fresh_42]

I think I'm having a hard time with this assignment because I:
(1) Have not learned about the Chinese root theorem
(2) Have not seen a similar assignment before
(3) Am very new to solving diophantine equations so
(4) I tend to approach solving them in one, very mechanical way:
1. Rewrite the equation $a\equiv b\pmod n\implies a=xn+bk\implies xn-bk=a$
2. Get a particular solution, either by directly seeing it or doing Euclidean algorithm in reverse
3. Given the particular solution $x_p$ we get $x=x_p+\frac{b}{gcd(n,b)}c, c\in \mathbb Z$

So when I encounter ways of solving diophantine equations that do not seem to do it in the way that I explained in (4), I get confused.

In your particular proposition, I do not see what insight I should get from that $m_2$ is odd.

This I understand intuitively now that you told me, but as I explained above (in (4)), I still approach diophantine equations in a very mechanical way. I would expect $648$ to be the result of $\frac{b}{gcd(n,b)}$ as in $x=x_p+\frac{b}{gcd(n,b)}c, c\in \mathbb Z$ (explained in (4.3) above). But I can't connect the fact that $648=8\cdot 81$ to my familar formulas (and I don't know where $b$ would come from in the first case), so I just have a hard time seeing the intuition behind the solution since I can't connect it to anything that I've worked with before.
If that makes any sense at all.

I suggest you first follow the way @PeroK has outlined. The only other method I know of would be the CRT (Chinese Remainder Theorem) and Wikipedia shows an algorithm for it. Without using it, use @PeroK's step-by-step method!

For the $648$ problematic, imagine you got a solution $x.$ The CRT got me $x=-5435.$ I haven't done it differently, so you might find $x=397$ or e.g. $x=-251$ or $x=1045$ or whatever. Say you got $397.$ Then you can mark it by the pair $(5,73)$ of remainders modulo $8$ and $81$ respectively. If you next color every eight numbers blue on the number line in both directions and every eighty-one numbers red on the number line in both directions, then $397$ is colored blue and red. Now, what will be the other numbers that are both, red and blue? All of them satisfy the conditions $x\equiv 5\pmod{8}$ and $x\equiv 73\pmod{81}$ simultaneously. All other numbers are either uncolored, only blue, or only red.

 

[PeroK]

I think I'm having a hard time with this assignment because I:
(1) Have not learned about the Chinese root theorem

I didn't use that.

(2) Have not seen a similar assignment before
(3) Am very new to solving diophantine equations so
(4) I tend to approach solving them in one, very mechanical way:

I thought my method was mechanical.

The question asks for integers whose remainder is 5 on division by 8 and whose remainder is 73 on division by 81. There must be an elementary solution for that. The only trick I used was to note where the second integer ($m$) was odd or even and break it down further.

The other thing you should do is check that the numbers you get ($397 + 648n$) all satisfy both the original equations. That's good practice even when you have a book answer.

 

[PeroK]

Another suggestion is to use a spreadsheet or write a computer program to do this. Here's a spreasheet. The first column starts at 73 and each row is the previous row plus 81. The second column is the first column mod 8. You can see the simple pattern as 8 and 81 are coprime (as identified by @fresh42). The third colum uses an IF to pick out where the second column is 5. The fourth column I did by hand to show the difference in the X's. And there's the answer!

x (73)	mod 8
73​	1​
154​	2​
235​	3​
316​	4​
397​	5​	X
478​	6​
559​	7​
640​	0​
721​	1​
802​	2​
883​	3​
964​	4​
1045​	5​	X	648​
1126​	6​
1207​	7​
1288​	0​
1369​	1​
1450​	2​
1531​	3​
1612​	4​
1693​	5​	X	648​
1774​	6​
1855​	7​
1936​	0​
2017​	1​
2098​	2​
2179​	3​
2260​	4​
2341​	5​	X	648​

 

[fresh_42]

Another suggestion is to use a spreadsheet or write a computer program to do this. Here's a spreasheet. The first column starts at 73 and each row is the previous row plus 81. The second column is the first column mod 8. You can see the simple pattern as 8 and 81 are coprime (as identified by @fresh42). The third colum uses an IF to pick out where the second column is 5. The fourth column I did by hand to show the difference in the X's. And there's the answer!

x (73)	mod 8
73​	1​
154​	2​
235​	3​
316​	4​
397​	5​	X
478​	6​
559​	7​
640​	0​
721​	1​
802​	2​
883​	3​
964​	4​
1045​	5​	X	648​
1126​	6​
1207​	7​
1288​	0​
1369​	1​
1450​	2​
1531​	3​
1612​	4​
1693​	5​	X	648​
1774​	6​
1855​	7​
1936​	0​
2017​	1​
2098​	2​
2179​	3​
2260​	4​
2341​	5​	X	648​

The number line in modern times!