Solution of a congruence

Question

Where is my mistake please tell ,I also tried $x \equiv 1 \pmod 7$ instead of $25x \equiv 4 \pmod 7$ and $7x \equiv 4 \pmod 9$ instead of $25x \equiv 4 \pmod 9$

I realize it's a fair amount of work, but you're better off typing up your work in MathJax. — Adrian Keister, Jun 25 '18 at 16:32
The multiplicative inverses of 4, are only mutiplicative inverses mod 7 and 9, not mod 63. So you must multiply them out in mod 7 and mod 9 before solving in mod 63. $7y \equiv 1 mod 9\implies y \equiv 4$ so $7x \equiv 4 \mod 9\implies x\equiv 4y \equiv 16 \equiv 7 \mod 9$. And $9w\equiv 1 \mod 7\implies w\equiv 4\mod 7$ so $9x \equiv 4 \implies x\equiv 4w \equiv 16\equiv 2\mod 7$. So $x \equiv 2\mod 7$and $x\equiv 7\mod 9$. and.... wait. What the heck is that $x_0 = 4(94) + 4(74)$ business? What the heck is that* supposed to do? — fleablood, Jun 25 '18 at 17:12
You use $x$ for three different values. You have $25x_1 \equiv 4 \mod 63$ and $9x_2\equiv 1 \mod 7$ and $7x_3 \equiv 1 \mod 7$ These are not nescesarily the same values. — fleablood, Jun 25 '18 at 17:49

score 0 · Answer 1 · answered Jun 25 '18 at 16:40

0

But $x=1$ works, $$25\equiv 4 \mod 7$$

answered Jun 25 '18 at 16:40

Dr. Sonnhard Graubner

95,283

Yes but I don't know why can you tell me why it doesn't work for x=4 – John757 Jun 25 '18 at 19:45
Can you tell me when I need to simplify the congruence and when it is appropriate for CRT? – John757 Jun 25 '18 at 19:48

score 0 · Accepted Answer · answered Jun 25 '18 at 16:43

The answer you give (i.e. $x\equiv 4\pmod{63}$) is incorrect; try putting in $x=4$ to the original congruence equation.

I don't really see why you need CRT. All you need to do is find the inverse of $25$ modulo $63$. This can be done by the Euclidean algorithm to find $a,b\in\Bbb Z$ such that $25a+63b=1$. Then $a$ is the inverse of $25$ modulo $63$, and we get $$25x\equiv 4\pmod{63}\iff x\equiv 4a\pmod {63}$$

Spoiler:

You should find that $a=-5$ and $b=2$ (I did this simply by inspection). So $$x\equiv 4\cdot (-5)\equiv -20\equiv 43\pmod{63}$$

I wanted an answer in crt but I appreciate the new method you introduced — John757, Jun 25 '18 at 19:44

score 0 · Answer 3 · answered Jun 25 '18 at 18:14

You solved for $x \equiv 4 \mod 63$.

You need to solve for $25 x \equiv 4 \mod 63$

$25 x\equiv 4x \equiv 4 \mod 7$ so $x \equiv 1 \mod 7$

And $25 x \equiv 7x \mod 4 \mod 9$ so a bit of finaggling... $7y \equiv 1 \mod 9 \implies y \equiv 4 \mod 9$ so $4*7*x \equiv x \equiv 4*4 \equiv 7 \mod 9$.

Now use the CRT to solve

$x \equiv 1 \mod 7$

$x \equiv 7 \mod 9$

This time you will get the correct answer

Solution of a congruence

3 Answers3