Solutions of an equation

**demode** · March 22nd 2011, 03:42 AM

I need some help with the following problem:

(a) Prove that the equation $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 $\mathbb{Z}_{568}$ and another one in $\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.

**Prove It** · March 22nd 2011, 04:11 AM

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

$\displaystyle x^2 = 41$ .

There is not an integer solution to this equation.

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

$\displaystyle x^2 + 23 = 41$

$\displaystyle x^2 = 18$ .

There is not an integer solution to this equation.

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

$\displaystyle x^2 + 92 = 41$

$\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 x^2 = \textrm{something negative}$ , which will not give any integer (or real) solution.

**alexmahone** · March 22nd 2011, 04:13 AM

Originally Posted by demode

I need some help with the following problem:

(a) Prove that the equation $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 $\mathbb{Z}_{568}$ and another one in $\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), $y^2$ can only be 0 or 1. (Otherwise x will not be real.)

So, we get two cases:

1) $x^2=41$

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

Clearly, neither of these equations have integral solutions.

I have no idea about part (b).

**Petek** · March 22nd 2011, 07:21 AM

For part (b) , observe that

$568 = 2^3 \cdot 71$

and

$657 = 3^2 \cdot 73$

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

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

and

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

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

**demode** · March 22nd 2011, 11:12 PM

Originally Posted by Petek

For part (b) , observe that

$568 = 2^3 \cdot 71$

and

$657 = 3^2 \cdot 73$

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

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

and

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

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

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

**Petek** · March 23rd 2011, 07:59 AM

Originally Posted by demode

How do you solve this kind of equations (like $4y \equiv 1 (mod \ 657)$ for example) without checking all different elements in $\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

$ax \equiv b (mod \ m)$

Solving the above congruence is equivalent to solving the diophantine equation

$ax - my = b$

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

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

is to observe that

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

Use Euler's theorem to conclude that

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

and so

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

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

Thread: Solutions of an equation

LinkBack

Thread Tools

Display

Solutions of an equation

Similar Math Help Forum Discussions

Equation has exactly 2 solutions

Equation solutions

Solutions to sin equation

Solutions to an equation.

Solutions to this diophantine equation.

Search Tags