Question

solve the following congruence
a) 17x=29(mod.37)
[= this is congruency symbol I coudnt type the symbol so kept =]​

Answer 1

We're given to solve the following congruence.

$\longrightarrow17x\equiv29\pmod{37}$

Then let,

$\longrightarrow17x=29+37a,\quad a\in\mathbb{Z}\quad\quad\dots(1)$

then each side is congruent to each other modulo the least coefficient (ignoring constant term) other than 1 there. Here it's 17.

$\longrightarrow17x\equiv29+37a\pmod{17}\quad\quad\dots(2)$

We see,

• $17\equiv0\pmod{17}$

• $29\equiv12\pmod{17}$

• $37\equiv3\pmod{17}$

Then (2) becomes,

$\longrightarrow0\equiv12+3a\pmod{17}$

We repeat the same process until we get any of the coefficient as 1.

Let,

$\longrightarrow0=12+3a+17b,\quad b\in\mathbb{Z}\quad\quad\dots(3)$

then we have,

$\longrightarrow0\equiv12+3a+17b\pmod{3}\quad\quad\dots(4)$

We see,

• $12\equiv0\pmod{3}$

• $3\equiv0\pmod{3}$

• $17\equiv2\pmod{3}$

Then (4) becomes,

$\longrightarrow0\equiv2b\pmod{3}$

Let,

$\longrightarrow0=2b+3c,\quad c\in\mathbb{Z}\quad\quad\dots(5)$

then we have,

$\longrightarrow0\equiv2b+3c\pmod{2}\quad\quad\dots(6)$

We see,

• $2\equiv0\pmod{2}$

• $3\equiv1\pmod{2}$

Then (6) becomes,

$\longrightarrow c\equiv0\pmod{2}$

It means $c$ is any multiple of 2. Here the coefficient is 1 so end up with here.

Let,

• $c=2k,\quad k\in\mathbb{Z}$

Then (5) becomes,

$\longrightarrow0=2b+3(2k)$

$\longrightarrow0=2b+6k$

$\longrightarrow b=-3k$

Then (3) becomes,

$\longrightarrow0=12+3a+17(-3k)$

$\longrightarrow0=12+3a-51k$

$\longrightarrow a=17k-4$

Then (1) becomes,

$\longrightarrow17x=29+37(17k-4)$

$\longrightarrow17x=29+37\cdot17k-37\cdot4$

$\longrightarrow17x=37\cdot17k-119$

$\longrightarrow\underline{\underline{x=37k-7}}$

This is the solution to our congruence.

Answer 2

Answer:

We're given to solve the following congruence.

\longrightarrow17x\equiv29\pmod{37}⟶17x≡29(mod37)

Then let,

\longrightarrow17x=29+37a,\quad a\in\mathbb{Z}\quad\quad\dots(1)⟶17x=29+37a,a∈Z…(1)

then each side is congruent to each other modulo the least coefficient (ignoring constant term) other than 1 there. Here it's 17.

\longrightarrow17x\equiv29+37a\pmod{17}\quad\quad\dots(2)⟶17x≡29+37a(mod17)…(2)

We see,

17\equiv0\pmod{17}17≡0(mod17)

29\equiv12\pmod{17}29≡12(mod17)

37\equiv3\pmod{17}37≡3(mod17)

Then (2) becomes,

\longrightarrow0\equiv12+3a\pmod{17}⟶0≡12+3a(mod17)

We repeat the same process until we get any of the coefficient as 1.

Let,

\longrightarrow0=12+3a+17b,\quad b\in\mathbb{Z}\quad\quad\dots(3)⟶0=12+3a+17b,b∈Z…(3)

then we have,

\longrightarrow0\equiv12+3a+17b\pmod{3}\quad\quad\dots(4)⟶0≡12+3a+17b(mod3)…(4)

We see,

12\equiv0\pmod{3}12≡0(mod3)

3\equiv0\pmod{3}3≡0(mod3)

17\equiv2\pmod{3}17≡2(mod3)

Then (4) becomes,

\longrightarrow0\equiv2b\pmod{3}⟶0≡2b(mod3)

Let,

\longrightarrow0=2b+3c,\quad c\in\mathbb{Z}\quad\quad\dots(5)⟶0=2b+3c,c∈Z…(5)

then we have,

\longrightarrow0\equiv2b+3c\pmod{2}\quad\quad\dots(6)⟶0≡2b+3c(mod2)…(6)

We see,

2\equiv0\pmod{2}2≡0(mod2)

3\equiv1\pmod{2}3≡1(mod2)

Then (6) becomes,

\longrightarrow c\equiv0\pmod{2}⟶c≡0(mod2)

It means cc is any multiple of 2. Here the coefficient is 1 so end up with here.

Let,

c=2k,\quad k\in\mathbb{Z}c=2k,k∈Z

Then (5) becomes,

\longrightarrow0=2b+3(2k)⟶0=2b+3(2k)

\longrightarrow0=2b+6k⟶0=2b+6k

\longrightarrow b=-3k⟶b=−3k

Then (3) becomes,

\longrightarrow0=12+3a+17(-3k)⟶0=12+3a+17(−3k)

\longrightarrow0=12+3a-51k⟶0=12+3a−51k

\longrightarrow a=17k-4⟶a=17k−4

Then (1) becomes,

\longrightarrow17x=29+37(17k-4)⟶17x=29+37(17k−4)

\longrightarrow17x=29+37\cdot17k-37\cdot4⟶17x=29+37⋅17k−37⋅4

\longrightarrow17x=37\cdot17k-119⟶17x=37⋅17k−119

\longrightarrow\underline{\underline{x=37k-7}}⟶

x=37k−7

This is the solution to our congruence.

Step-by-step explanation:

mark me as branlinst