Question and Answers Forum

All Questions      Topic List

Coordinate Geometry Questions

Previous in All Question      Next in All Question      

Previous in Coordinate Geometry      Next in Coordinate Geometry      

Question Number 107594 by Rio Michael last updated on 11/Aug/20

$$\mathrm{Find}\mathrm{the}\mathrm{greatest}\mathrm{common}\mathrm{divisor}\mathrm{of}1122\mathrm{and}1001\mathrm{and}$$$$\mathrm{express}\mathrm{the}\mathrm{greatest}\mathrm{common}\mathrm{divisor}d\mathrm{in}\mathrm{the}\mathrm{form}.$$$$d=1122x+1001y$$$$\mathrm{Using}\mathrm{the}\mathrm{above}\mathrm{result}\mathrm{solve}\mathrm{the}\mathrm{congruence}\mathrm{equation}$$$$37x\equiv 11\left(\mathrm{mod}33\right)$$

Answered by 1549442205PVT last updated on 11/Aug/20

$$37\mathrm{x}-11=33\mathrm{y}\iff \mathrm{y}=\frac{37\mathrm{x}-11}{33}=\mathrm{x}+\frac{4\mathrm{x}-11}{33}$$$$\mathrm{Set}\frac{4\mathrm{x}-11}{33}=\mathrm{t}(\mathrm{t}\in \mathbb{Z})\Rightarrow 4\mathrm{x}-11=33\mathrm{t}$$$$\iff \mathrm{x}=\frac{33\mathrm{t}+11}{4}=8\mathrm{t}+3+\frac{\mathrm{t}-1}{4}.\mathrm{Set}\frac{\mathrm{t}-1}{4}=\mathrm{k}$$$$\Rightarrow \mathrm{t}=4\mathrm{k}+1(\mathrm{k}\in \mathbb{Z})\mathrm{we}\mathrm{get}$$$$\{\begin{array}{l}\mathrm{x}=33\mathrm{k}+11\\ \mathrm{y}=37\mathrm{k}+12\end{array}(\mathrm{k}\in \mathbb{Z})$$

Answered by Aziztisffola last updated on 11/Aug/20

$$\mathrm{we}\mathrm{have}\gcd (1122;1001)=11=\mathrm{d}$$$$1122x+1001y=11$$$$\mathrm{and}37x\equiv 11\left(\mathrm{mod}33\right)\iff \mathrm{\exists }k\in \mathbb{Z}37x-33k=11$$$$\Rightarrow 37x-33k=11=1122x+1001y$$$$\mathrm{Using}\mathrm{Gauss}\mathrm{theorem}\mathrm{we}\mathrm{get}$$$$\mathrm{x}=33\mathrm{k}+11$$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com