Proove that x exists such that x^2 is congruent with -1 (mod 2038) and give an example solution
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)