# Thread: Solutions of an equation

1. ## Solutions of an equation

I need some help with the following problem:

(a) Prove that the equation $\displaystyle x^2 + 23y^2 = 41$ does not have solutions in integers.

(b) If (1/3, 4/3) and (9/4, 5/4) are two rational solutions of this equation, find a solution to this equation in $\displaystyle \mathbb{Z}_{568}$ and another one in $\displaystyle \mathbb{Z}_{657}$.

I have not encountered this type of problems before, so I'm unsure how to get started on either parts. Any help to get me started on them is greatly appreciated.

2. If youl let $\displaystyle \displaystyle y = 0$, then you have

$\displaystyle \displaystyle x^2 = 41$.

There is not an integer solution to this equation.

If you let $\displaystyle \displaystyle y = \pm 1$, then you have

$\displaystyle \displaystyle x^2 + 23 = 41$

$\displaystyle \displaystyle x^2 = 18$.

There is not an integer solution to this equation.

If you let $\displaystyle \displaystyle y = \pm 2$, you have

$\displaystyle \displaystyle x^2 + 92 = 41$

$\displaystyle \displaystyle x^2 = -51$ which also does not have any integer (or real) solutions.

It should also be clear that any other integer will also give $\displaystyle \displaystyle x^2 = \textrm{something negative}$, which will not give any integer (or real) solution.

3. Originally Posted by demode
I need some help with the following problem:

(a) Prove that the equation $\displaystyle x^2 + 23y^2 = 41$ does not have solutions in integers.

(b) If (1/3, 4/3) and (9/4, 5/4) are two rational solutions of this equation, find a solution to this equation in $\displaystyle \mathbb{Z}_{568}$ and another one in $\displaystyle \mathbb{Z}_{657}$.

I have not encountered this type of problems before, so I'm unsure how to get started on either parts. Any help to get me started on them is greatly appreciated.
For part (a), $\displaystyle y^2$ can only be 0 or 1. (Otherwise x will not be real.)

So, we get two cases:

1) $\displaystyle x^2=41$

2) $\displaystyle x^2+23=41 \implies x^2=18$

Clearly, neither of these equations have integral solutions.

I have no idea about part (b).

4. For part (b) , observe that

$\displaystyle 568 = 2^3 \cdot 71$

and

$\displaystyle 657 = 3^2 \cdot 73$

Therefore, gcd(3,568) = 1 and gcd(4,657) = 1. It follows that each of the equations

$\displaystyle 3x \equiv 1 (mod \ 568)$

and

$\displaystyle 4y \equiv 1 (mod \ 657)$

has a solution in $\displaystyle \mathbb{Z}$. Can you take it from there?

5. Originally Posted by Petek
For part (b) , observe that

$\displaystyle 568 = 2^3 \cdot 71$

and

$\displaystyle 657 = 3^2 \cdot 73$

Therefore, gcd(3,568) = 1 and gcd(4,657) = 1. It follows that each of the equations

$\displaystyle 3x \equiv 1 (mod \ 568)$

and

$\displaystyle 4y \equiv 1 (mod \ 657)$

has a solution in $\displaystyle \mathbb{Z}$. Can you take it from there?
How do you solve this kind of equations (like $\displaystyle 4y \equiv 1 (mod \ 657)$ for example) without checking all different elements in $\displaystyle \mathbb{Z}_{657}$? Do you somehow use the prime power factorization?

6. Originally Posted by demode
How do you solve this kind of equations (like $\displaystyle 4y \equiv 1 (mod \ 657)$ for example) without checking all different elements in $\displaystyle \mathbb{Z}_{657}$? Do you somehow use the prime power factorization?
If you're studying a number theory textbook (or have access to one), it should have a section on solving linear congruences of the form

$\displaystyle ax \equiv b (mod \ m)$

Solving the above congruence is equivalent to solving the diophantine equation

$\displaystyle ax - my = b$

which can be solved, for example by the Euclidean algorithm or continued fractions. Another way to solve the equation

$\displaystyle 4y \equiv 1 (mod \ 657)$

is to observe that

$\displaystyle \phi(657) = \phi(3^2) \cdot \phi(73) = 3 \cdot 72 = 216$

Use Euler's theorem to conclude that

$\displaystyle 4^{\phi(657)} \equiv 1 (mod \ 657)$

and so

$\displaystyle 4 \cdot 4^{215} \equiv 1 (mod \ 657)$

Then simplify $\displaystyle 4^{215}$ mod 657.