Question

To determine: The smallest nonnegative integer x that satisfies the given system of congruences. x\equiv 1\pmod {4} x\equiv 8\pmod {9} x\equiv 10\pmod{25}

Congruence
ANSWERED
asked 2021-05-06
To determine: The smallest nonnegative integer x that satisfies the given system of congruences.
\(\displaystyle{x}\equiv{1}\pm{o}{d}{\left\lbrace{4}\right\rbrace}\)
\(\displaystyle{x}\equiv{8}\pm{o}{d}{\left\lbrace{9}\right\rbrace}\)
\(\displaystyle{x}\equiv{10}\pm{o}{d}{\left\lbrace{25}\right\rbrace}\)

Answers (1)

2021-05-08

\(\displaystyle{x}\equiv{1}\pm{o}{d}{\left\lbrace{4}\right\rbrace}\)
\(\displaystyle{x}\equiv{8}\pm{o}{d}{\left\lbrace{9}\right\rbrace}\)
\(\displaystyle{x}\equiv{10}\pm{o}{d}{\left\lbrace{25}\right\rbrace}\)
First let us solve the first two congruences.
\(\displaystyle{x}\equiv{1}\pm{o}{d}{\left\lbrace{4}\right\rbrace}\)
\(\displaystyle{x}\equiv{8}\pm{o}{d}{\left\lbrace{9}\right\rbrace}\)
We see that the solution x is unique modulo \(4.9=36\).
Now, \(9-4(2)=1\).
Thus,
\(x=1.9-8.4(2)\)
\(x=9-64\)
\(x=-55\)
\(\displaystyle{x}=-{19}\pm{o}{d}{\left\lbrace{36}\right\rbrace}\)
\(\displaystyle{x}={17}\pm{o}{d}{\left\lbrace{36}\right\rbrace}\)
Therefore, \(\displaystyle{x}={17}\pm{o}{d}{\left\lbrace{36}\right\rbrace}\).
Now, let us solve the below equations.
\(\displaystyle{x}\equiv{17}\pm{o}{d}{\left\lbrace{36}\right\rbrace}\)
\(\displaystyle{x}\equiv{10}\pm{o}{d}{\left\lbrace{25}\right\rbrace}\)
We see that the solution x is unique modulo \(36.25=900\).
Now, \(25(13)-36(9)=1\).
Thus,
\(x=17.25(13)-10.36(9)\)
\(x=5525-3240\)
\(x=2285\)
\(\displaystyle{x}={485}\pm{o}{d}{\left\lbrace{900}\right\rbrace}\)
Therefore, \(x = 485.\)

0
 
Best answer

expert advice

Need a better answer?
...