This is a subject in discrete mathematics / discrete Structure. My question is about congruences, I don't seem to be understand the concept in congruence equations.

I understand that 10 mod 3= 1, there is a question and the professor provided answer for it, but I don't understand the answer fully.

4. Number theory, GCD, inverse, linear congruence equation

(1) The Bezout’s identity gcd(2, 17) = 2s + 17t can be derived as follows: 17 = 8*2 + 1

2 =2*1

From the first equation we obtain 1 = 17 - 8*2, -- I understand how this came about --

 

then we get gcd(2, 17) = - 8*2 + 17,

and thus - 8*2 ≡ 1 mod 17. Therefore x ≡ -8 ≡ 9 mod 17 is the inverse of 2 mod 17. -- confused about the inverse not quite understanding it --

(2)From12x^2 +25x+12=(3x+4)(4x+3)≡0mod11,wehave3x+4≡0mod11,or4x+3≡0mod11.

(i) The first congruence equation could be expresses as 3x ≡ -4 mod 11. Since we have gcd(3, 11) = 1, the Bezout’s identity gcd(3, 11) = 3s + 11t can be derived as follows:

11 = 3*3 + 2

3 =1*2+1

2 =2*1

From the second equation we obtain 1 = 3 - 2,

and replace 2 with the result from the first equation 2 = 11 - 3*3, we get 1 = 3 - (11 - 3*3) = -11 + 4*3, i.e. gcd(3, 11) = 4*3 -1*11, and thus 4*3 ≡ 1 mod 11 (4 is the inverse of 3 mod 11).

To solve the congruence equation 3x ≡ -4 mod 11,

multiply -4 on both sides of the equation 4*3 ≡ 1 mod 11, we get -4*4*3 ≡ -4 mod 11,

therefore x ≡ -16 ≡ 6 mod 11 is the solution of the first congruence equation.

(ii) The second congruence equation could be expressed as 4x ≡ -3 mod 11. Since we have gcd(4, 11) = 1, the Bezout’s identity gcd(4, 11) = 4s + 11t can be derived as follows:

11 = 2*4 + 3

4 =1*3+1

3 =3*1

From the second equation we obtain 1 = 4 - 3,

and replace 3 with the result from the first equation 3 = 11 - 2*4, we get 1 = 4 - (11 - 2*4) = -11 + 3*4, i.e. gcd(4, 11) = 3*4 -1*11, and thus 3*4 ≡ 1 mod 11 (3 is the inverse of 4 mod 11).

To solve the congruence equation 4x ≡ -3 mod 11,

multiply -3 on both sides of the equation 3*4 ≡ 1 mod 11, we get -3*3*4 ≡ -3 mod 11,

therefore x ≡ -9 ≡ 2 mod 11 is the solution of the first congruence equation.

From above results we can conclude the solutions of the congruence 12x^2 + 25x ≡ 10 mod 11 are x ≡ 6 mod 11, or x ≡ 2 mod 11

SophiaPretty

(5)

Status NEW Posted 28 Nov 2017 10:11 AM My Price 8.00

-----------  ----------- H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly

Not Rated(0)

• Buy Answer