Proove that x exists such that x^2 is congruent with -1 (mod 2038) and give an example solution

### 1 Answer | Add Yours

Euler's Theorem states that if `a` and `n` are coprime then

`a^(phi(n)) -= 1` `mod n`

` ` ` `where `phi` is Euler's `phi` function (which gives the number of numbers less than or equal to `n` that are coprime with `n`).

Also, Euler's product formula says that

`phi(n) = n prod_(p(n)) (1-1/p)`

where the product is taken over all prime factors of `n`.

We begin by writing 2038 in prime factorisation form: 2038 = 2 x 1019

Therefore

`phi(2038) = 2038(1-1/2)(1-1/1019) `

`= 2038(1/2)(1018/1019) = 1018`

Now, we are looking for `x` such that

`x^2 + 2 -= 1` `mod 2038`

Such an `x` could satisfy

`x^2 + 2 = a^(phi(2038)) = a^1018` where `a` is coprime with ` ``n`, or equivalently

`x^2 = a^1018-2` which implies that

`x = pm sqrt(a^1018-2)`

Since 2038 has only the prime factors 2 and 1019, there are real solutions for x provided a is an odd integer within the range [3,2037] and not equal to 1019.

**For example we could have a = 3, giving**

**`x = pm sqrt(3^1018-2)` (incalculably large, but nevertheless a solution)**

### Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes