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

Expert Answers

An illustration of the letter 'A' in a speech bubbles

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


`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)



Approved by eNotes Editorial Team

We’ll help your grades soar

Start your 48-hour free trial and unlock all the summaries, Q&A, and analyses you need to get better grades now.

  • 30,000+ book summaries
  • 20% study tools discount
  • Ad-free content
  • PDF downloads
  • 300,000+ answers
  • 5-star customer support
Start your 48-Hour Free Trial