Question Number 96928 by bobhans last updated on 05/Jun/20 | ||
$$\mathrm{69}{x}\:\equiv\:\mathrm{1}\:\left(\mathrm{mod}\:\mathrm{31}\right)\: \\ $$$$\mathrm{solve}\:\mathrm{for}\:{x} \\ $$ | ||
Commented by RAMANA last updated on 05/Jun/20 | ||
$${send}\:{the}\:{answer}\:{please} \\ $$ | ||
Answered by MAB last updated on 05/Jun/20 | ||
$$\mathrm{69}{x}\equiv\mathrm{1}\left[\mathrm{31}\right] \\ $$$$\mathrm{69}{x}−\mathrm{31}×\mathrm{2}×{x}\equiv\mathrm{1}\left[\mathrm{31}\right] \\ $$$$\mathrm{7}{x}\equiv\mathrm{1}\left[\mathrm{31}\right] \\ $$$${we}\:{have}\:\mathrm{31}\:{is}\:{prime}\:{and}\:\mathrm{7}{x}\equiv\mathrm{1}\left[\mathrm{31}\right]\: \\ $$$${and}\:{the}\:{only}\:{inverse}\:{of}\:\mathrm{7}\:{in}\:{the}\:{class}\:\mathrm{31} \\ $$$${is}\:\mathrm{9}\:\left(\:\mathrm{7}×\mathrm{9}=\mathrm{63}=\mathrm{2}×\mathrm{31}+\mathrm{1}\right) \\ $$$${therfore}\:{x}\equiv\:\left[\mathrm{31}\right] \\ $$ | ||
Answered by 1549442205 last updated on 06/Jun/20 | ||
$$\mathrm{we}\:\mathrm{have}\:\mathrm{69x}−\mathrm{1}=\mathrm{31a}\left(\mathrm{a}\in\mathbb{Z}\right)\Leftrightarrow\mathrm{a}=\frac{\mathrm{69x}−\mathrm{1}}{\mathrm{31}}=\mathrm{2x}+\frac{\mathrm{7x}−\mathrm{1}}{\mathrm{31}} \\ $$$$\Rightarrow\mathrm{7x}−\mathrm{1}=\mathrm{31b}\left(\mathrm{b}\in\mathbb{Z}\right)\Leftrightarrow\mathrm{x}=\frac{\mathrm{31b}+\mathrm{1}}{\mathrm{7}}=\mathrm{4b}+\frac{\mathrm{3b}+\mathrm{1}}{\mathrm{7}} \\ $$$$\Rightarrow\mathrm{3b}+\mathrm{1}=\mathrm{7c}\left(\mathrm{c}\in\mathbb{Z}\right)\Leftrightarrow\mathrm{b}=\frac{\mathrm{7c}−\mathrm{1}}{\mathrm{3}}=\mathrm{2c}+\frac{\mathrm{c}−\mathrm{1}}{\mathrm{3}} \\ $$$$\Rightarrow\mathrm{c}−\mathrm{1}=\mathrm{3d}\left(\mathrm{d}\in\mathbb{Z}\right)\Rightarrow\boldsymbol{\mathrm{c}}=\mathrm{3}\boldsymbol{\mathrm{d}}+\mathrm{1}.\mathrm{From}\:\mathrm{this}\:\mathrm{we}\:\mathrm{get} \\ $$$$\boldsymbol{\mathrm{b}}=\mathrm{2}\boldsymbol{\mathrm{c}}+\boldsymbol{\mathrm{d}}=\mathrm{7}\boldsymbol{\mathrm{d}}+\mathrm{2}\Rightarrow\boldsymbol{\mathrm{x}}=\mathrm{4}\boldsymbol{\mathrm{b}}+\boldsymbol{\mathrm{c}}=\mathrm{31}\boldsymbol{\mathrm{d}}+\mathrm{9} \\ $$$$\boldsymbol{\mathrm{Thus}},\boldsymbol{\mathrm{x}}=\mathrm{31}\boldsymbol{\mathrm{d}}+\mathrm{9}\:\boldsymbol{\mathrm{or}}\:\boldsymbol{\mathrm{x}}=\mathrm{9}\left(\boldsymbol{\mathrm{mod}}\mathrm{31}\right) \\ $$ | ||
Answered by mr W last updated on 06/Jun/20 | ||
$$\mathrm{69}{x}=\mathrm{31}{n}+\mathrm{1} \\ $$$$\mathrm{69}{x}−\mathrm{31}{n}=\mathrm{1} \\ $$$$\Rightarrow{x}=\mathrm{31}{k}+\mathrm{9}\:\Rightarrow{x}\equiv\mathrm{9}\:{mod}\:\mathrm{31} \\ $$$$ \\ $$$${see}\:{also}\:{Q}\mathrm{44704},\:{Q}\mathrm{19198} \\ $$ | ||