Homework Help

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

user profile pic

svjr | Student, Undergraduate | Honors

Posted October 9, 2011 at 10:16 PM via web

dislike 1 like

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

1 Answer | Add Yours

user profile pic

mathsworkmusic | (Level 3) Associate Educator

Posted April 29, 2013 at 12:28 PM (Answer #1)

dislike 1 like

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