The Solution of the Indefinite Equation by the Method of Euclidean Algorithm

Zhongqi Zhou

Hubei Coal Geology Bureau, Wuhan, China.

DOI: 10.4236/oalib.1112011                

Abstract

In this paper, a new mathematical method is used to study the indefinite equations of binary quadratic and binary arbitrary order, the problem of judging and solving these indefinite equations with or without solutions is solved.

Keywords

Euclidean Algorithm, Binary Quadratic Indefinite Equation, Indefinite Equation of Higher Order in Binary, Positive Integer Solutions

1. Introduction

On the whole, there is no uniform method to solve the indefinite equations of more than two degrees, but some results have been obtained for some special equations of higher order [1].

If a positive integer can be expressed as the sum of squares of two numbers, it is generally difficult to give a formula to express its solution in detail [2].

The study of indefinite equation $m=q{x}^n+p{y}^n\left(n\ge 3\right)$ is very rare, and there is no general determination method for this kind of indefinite equation with and without solutions, and there is no general method for solving it.

In this paper, the following problems will be solved by using the Euclidean algorithm:

1) A general solution for $m=x^2+y^2$ is given (its solution is expressed in a formula).

2) Give a determination method for $m=q{x}^n+p{y}^n\left(n\ge 2\right)$ with or without solutions.

3) A general solution for $m=q{x}^n+p{y}^n$ is given.

2. Definition

Definition 1

Let $q,p\in N^{+}$ , $m\ge 3$ , $q,p,m$ are all given positive integer, if $m|q{z}^n+p$ , then

$q{z}^n\equiv -p\left(\mathrm{mod}m\right)$ (1)

For the solution of congruence (1), see [3].

Definition 2

Let $m>3$ is a known positive integer, $q{a}^n\equiv -p\left(\mathrm{mod}m\right)$ , $q,p$ is a known positive integer, $n\ge 2$ , $\left(q,p\right)=1$ , define the following procedure as m and $a$ Euclidean algorithm.

Denoted by the symbol: $\overleftrightarrow{{\left(m\text{,}a\right)}_{q{a}^n\equiv -p\left(\mathrm{mod}m\right)}}$.

$m=q_{1}a+r_1$ $0<r_1<a$ (2)

$a=q_2{r}_1+r_2$ $0<r_2<r_1$ ， (3)

$r_1=q_3{r}_2+r_3$ $0<r_3<r_2$ , (4)

$⋮$ $⋮$

$r_{i-3}=q_{i-1}{r}_{i-2}+r_{i-1}$ $q{r}_{i-1}^n>m$ , $0<r_{i-1}<r_{i-2}$ , (5)

$r_{i-2}=q_i{r}_{i-1}+r_i$ $q{r}_i^n<m$ , $0<r_i<r_{i-1}$ , (6)

$⋮$ $⋮$

3. Lemma

Lemma [4] Let m and $a$ be positive integers, and do the Euclidean algorithm:

$m=q_{1}a+r_1$ , $0<r_1<a$

$a=q_2{r}_1+r_2$ , $0<r_2<r_1$

$⋮$ $⋮$

$r_{k-2}=q_k{r}_{k-1}+r_k$ , $0<r_k<r_{k-1}$

$⋮$ $⋮$

record

$s_0=1,s_1=q_1,s_k=q_k{s}_{k-1}+s_{k-2},k\ge 2$

$l_0=0,l_1=1,l_k=q_k{l}_{k-1}+l_{k-2},k\ge 2$

then

$m{l}_k-a{s}_k={\left(-1\right)}^{k-1}{r}_k.$ (7)

4. Theorems

Theorem 1. Let all positive integer of $m>3$ , $z^2\equiv -1\left(\mathrm{mod}m\right)$ less than $\frac{m}{2}$

be solved as: $a_1,a_2,\cdots ,a_k$ . Then m and $a_t$ Euclidean algorithm, $m=x^2+y^2$ for all positive integer solution. $t=1,\cdots ,k$ . $m-a_t$ is the negative integer solution (the same result is obtained with all negative integer solutions).

Proof: Let’s prove that $m=x^2+y^2$ has a positive integer solution:

From $a_t^2\equiv -1\left(\mathrm{mod}m\right)$ , we know: $a_t^2+1=lm$ , l is a positive integer, m is a factor of $a_t^2+1$ , and $a_t^2+1$ has only prime factor of 2 and 4n + 1, so m also has only prime factors of 2 and 4s + 1, therefore, $m=x^2+y^2$ has positive integer solutions [5].

$\overleftrightarrow{{\left(m\text{,}{a}_t\right)}_{a_t^2\equiv -1\left(\mathrm{mod}m\right)}}$ and according to (7) obtain:

$m{l}_j-a_t{s}_j={\left(-1\right)}^{j-1}{r}_j\text{.}$ (8)

Modulo m to (8) to obtain the congruence:

${\left(-1\right)}^{j-1}\times r_j\equiv -s_j{a}_t\left(\mathrm{mod}m\right)$ (9)

Let square both sides of (9):

$r_j^2\equiv s_j^2\times a_t^2\left(\mathrm{mod}m\right)$ (10)

Since $a_t^2\equiv -1\left(\mathrm{mod}m\right)$ , the congruence (10) morphs into:

$r_j^2+s_j^2\equiv \text{0}\left(\mathrm{mod}m\right)$ .

Or $r_j^2+s_j^2=l_{j}m$ (11)

$l_j$ is a positive integer.

From $a_t^2\equiv -1\left(\mathrm{mod}m\right)$ we know that: $\left(a,m\right)=1$ , take $\overleftrightarrow{{\left(m\text{,}{a}_t\right)}_{a_t^2\equiv -1\left(\mathrm{mod}m\right)}}$, always get the following result:

$m=q_1{a}_t+r_1$ $0<r_1<r_0=a_t$ ,

$a=q_2{r}_1+r_2$ $0<r_2<r_1$ ,

$r_1=q_3{r}_2+r_3$ $0<r_3<r_2$ ,

$⋮$ $⋮$

$r_{i-3}=q_{i-1}{r}_{i-2}+r_{i-1}$ $r_{i-1}^2>m$ , $0<r_{i-1}<r_{i-2}$ ,

$r_{i-2}=q_i{r}_{i-1}+r_i$ $r_i^2<m$ , $0<r_i<r_{i-1}$ ,

$⋮$ $⋮$

$r_{k-2}=q_k{r}_{k-1}+r_k$ $r_k=1$ .

According to the above result and (7), a further result can be obtained:

When k is even:

$s_1=r_{k-\left(1-1\right)}=r_k,s_2=r_{k-\left(2-1\right)}=r_{k-1},\cdots ,s_k=r_{k-\left(k-1\right)}=r_1.$

$r_{\frac{k}{2}}=r_i\left(r_i^2<m,r_{i-1}^2>m\right),s_i=s_{\frac{k}{2}}=r_{k-\left(\frac{k}{2}-1\right)}=r_{\frac{k}{2}+1}=r_{i+1}.$

When k is odd:

$s_1=r_{k-1},s_2=r_{k-2},\cdots ,s_j=r_{k-j},\cdots ,s_k=r_{k-k}=r_0=a_t.$

$r_{\frac{k-1}{2}}=r_i\left(r_i^2<m,r_{i-1}^2>m\right),s_i=s_{\frac{k-1}{2}}=r_{k-\frac{k-1}{2}}=r_{\frac{k+1}{2}}=r_{i+1}.$

According to the above result:

$s_i=r_{i+1}.$

Since $r_{i+1}<r_i$ , according to (6) of definition 2: $r_i^2<m$ , so the $r_{i+1}^2=s_i^2<r_i^2<m$ .

According to (11) we get $r_i^2+s_i^2=l_{i}m$ , since $l_i$ is a positive integer, therefore

$l_i=1$ .

Resulting in: $m=r_i^2+s_i^2=r_i^2+r_{i+1}^2$ . That is $x=r_i,y=r_{i+1}$ .

Inference:

According to theorem 1, for any positive integer m, as long as there is $a$ , such that $a^2\equiv -1\left(\mathrm{mod}m\right)$ , then a positive integer solution of $m=x^2+y^2$ can be obtained by Euclidean algorithm, the following indefinite equations can obtained by this method:

$m=x^2+y^2,m=2^{\alpha }{p}_1^{{\alpha }_1}\cdots p_r^{{\alpha }_r},p_s\equiv 1\left(\mathrm{mod}4\right),s=1,2,\cdots ,r;\alpha =0,1.$

Example 1. Find all positive integer solutions for $\text{28249}=x^2+y^2$ .

Solving the congruence $z^2\equiv -1\left(\mathrm{mod}28249\right)$ yields the following four positive integer solutions:

$606,6118,11266,11471.$

$\overleftrightarrow{{\left(28249,606\right)}_{{606}^2\equiv -1\left(\text{mod28249}\right)}}$ Giving: $r_i=140,r_{i+1}=93;x_1=140,y_1=93$ .

$\overleftrightarrow{{\left(28249,6118\right)}_{{6118}^2\equiv -1\left(\text{mod28249}\right)}}$ Giving: $r_i=157,r_{i+1}=60;x_2=157,y_2=60$ .

$\overleftrightarrow{{\left(28249,11266\right)}_{{11266}^2\equiv -1\left(\text{mod28249}\right)}}$ Giving: $r_i=168,r_{i+1}=5;x_3=168,y_3=5$ .

$\overleftrightarrow{{\left(28249,11471\right)}_{{11471}^2\equiv -1\left(\text{mod28249}\right)}}$ Giving: $r_i=165,r_{i+1}=32;x_4=165,y_4=32$ .

Theorem 2. Set the $q,p\ge 1$ , for a given positive integer, $\left(qx,py\right)=1$ , $n\ge 2$ , if $q{z}^n\equiv -p\left(\mathrm{mod}m\right)$ no positive integer solutions, then

$m=q{x}^n+p{y}^n$

No positive integer solution.

Proof: If $m=q{x}^n+p{y}^n$ has a positive integer solution, set it as: $\left(x_0,y_0\right)$ , that is:

$m=q{x}_0^n+p{y}_0^n,q{x}_0^n\equiv -p{y}_0^n\left(\mathrm{mod}m\right),q{\left(\frac{x_0}{y_0}\right)}^n\equiv -p\left(\mathrm{mod}m\right).$

When the $\frac{x_0}{y_0}\equiv a\left(\mathrm{mod}m\right)$ , then $q{a}^n\equiv -p\left(\mathrm{mod}m\right)$ , with the $q{z}^n\equiv -p\left(\mathrm{mod}m\right)$ unsolved contradictions.

Theorem 3. Set the $q,p\ge 1$ , m > 1, for a given positive integer, $\left(qx,py\right)=1$ , $n\ge 2$ , if $q{z}^n\equiv \left(p\mathrm{mod}m\right)\left(\mathrm{mod}m\right)$ no positive integer solutions, then

$m=q{x}^n-p{y}^n$

No positive integer solution.

Proof: If $m=q{x}^n-p{y}^n$ has a positive integer solution, set it as: $\left(x_0,y_0\right)$ , that is:

$m=q{x}_0^n-p{y}_0^n,q{x}_0^n\equiv \left(p\mathrm{mod}m\right)y_0^n\left(\mathrm{mod}m\right),q{\left(\frac{x_0}{y_0}\right)}^n\equiv \left(p\mathrm{mod}m\right)\left(\mathrm{mod}m\right).$

When the $\frac{x_0}{y_0}\equiv a\left(\mathrm{mod}m\right)$ , then $q{a}^n\equiv \left(p\mathrm{mod}m\right)\left(\mathrm{mod}m\right)$ , with the $q{z}^n\equiv \left(p\mathrm{mod}m\right)\left(\mathrm{mod}m\right)$ unsolved contradictions.

Theorem 4. m is a given positive integer no nth power factor, $n\ge 2$ . $q,p\ge 1$ are all given positive integer, without nth power factors. $\left(q,p\right)=1$ , $q{z}^n\equiv -p\left(\mathrm{mod}m\right)$ for all positive integers less than m are solved as:

$a_1,a_2,\cdots ,a_k$ . $t=1,\cdots ,k$ . (when n is even, only take all positive integer solutions

less than $\frac{m}{2}$ , since $m-a_t$ and $a_t$ yield the same result).

Respectively $\overleftrightarrow{{\left(m\text{,}{a}_t\right)}_{q{a}_t^n\equiv -p\left(\mathrm{mod}m\right)}}$ and according to (7), respectively

${\left(-1\right)}^{i-1}\times r_i=l_{i}m-s_{i}a$ (12)

When n is even, if for some $a_t$ , when $q{r}_{i-1}^n>m$ , $q{r}_i^n<m$ , $p{s}_i^n<m$ , then $m=q{x}^n+p{y}^n$ there are positive integer solutions.

When n is odd, if for some $a_t$ such that i is even and

$q{r}_{i-1}^n>m,q{r}_i^n<m,p{s}_i^n<m,$

Then

$m=q{x}^n+p{y}^n$ there are positive integer solution.

If for all $a_t$ such that $q{r}_{i-1}^n>m,q{r}_i^n<m,p{s}_i^n>m$ and when n is odd, i is odd, then $m=q{x}^n+p{y}^n$ there is not positive integer solution.

Proof: take (12) modulo m to get:

${\left(-1\right)}^{i-1}\times r_i\equiv -s_i{a}_t\left(\mathrm{mod}m\right)$ (13)

If n is even, raise both sides of (13) to the power n and multiply q to get:

$q{r}_i^n\equiv s_i^{n}q{a}_t^n\left(\mathrm{mod}m\right)$

Since $q{a}_t^n\equiv -p\left(\mathrm{mod}m\right)$ , $q{r}_i^n+p{s}_i^n\equiv \text{0}\left(\mathrm{mod}m\right)$ , $q{r}_i^n+p{s}_i^n=l_{i}m$ .

According to (6) of the definition of $\overleftrightarrow{{\left(m\text{,}{a}_t\right)}_{q{a}_t^n\equiv -p\left(\mathrm{mod}m\right)}}$: $q{r}_i^n<m$ , if one $p{s}_i^n<m$ .

Then

$m=q{r}_i^n+p{s}_i^n\text{.}$

If n is odd, raise both sides of (13) to the power n and multiply by q:

${\left(-1\right)}^{i-1}q{r}_i^n\equiv -s_i^{n}q{a}_t^n\left(\mathrm{mod}m\right)$ (14)

If there is an $a_t$ , such that i is even and $p{s}_i^n<m$ , because $q{a}_t^n\equiv -p\left(\mathrm{mod}m\right)$ ,

Then (14) become:

$q{r}_i^n+p{s}_i^n\equiv 0\left(\mathrm{mod}m\right)$

If there is a $a_t$ such that i is even and $p{s}_i^n<m$ , from the definition of$\overleftrightarrow{{\left(m\text{,}{a}_t\right)}_{q{a}_t^n\equiv -p\left(\mathrm{mod}m\right)}}$ We know: $q{r}_i^n<m$ , therefore

$q{r}_i^n+p{s}_i^n=m\text{.}$

If for all $a_t$ such that $p{s}_i^n>m$ and when n is odd, i is odd, then $m=q{x}^n+p{y}^n$ .

There are not positive integer solution.

This is because: when n is even, there is for any j:

$q{r}_j^n+p{s}_j^n=l_{j}m\text{.}$

When $j>i$ , $s_j>s_i$ , $p{s}_j^n>m$ , when $j<i$ , $q{r}_j^n>m$ , so, for any j have:

$q{r}_j^n+p{s}_j^n>m\text{.}$

When n is odd and i is odd, $q{r}_i^n-p{s}_i^n=l_{i}m$ . $q{r}_i^n+p{s}_i^n\ne m$ .

Example 2. Find the positive integer solution of $14978=3x^3+5y^3$ .

Solving the congruence $3z^3\equiv -5\left(\mathrm{mod}14978\right)$ yields the following 3 positive integer.

Solution: 1153,7705,13609.

$\overleftrightarrow{{\left(\text{14978,1153}\right)}_{3\times {1153}^3\equiv -5\left(\mathrm{mod}14978\right)}}$ is obtained: $r_i=r_2=11$ , $s_i=13$ , $\text{5}\times {\text{13}}^{\text{3}}<14978$ .

$\overleftrightarrow{{\left(\text{14978,7705}\right)}_{3\times {7705}^3\equiv -5\left(\mathrm{mod}14978\right)}}$ is obtained $r_i=r_5=6$ , $s_5=208$ , n is odd, i is odd.

$\overleftrightarrow{{\left(\text{14978,13609}\right)}_{3\times {13609}^3\equiv -5\left(\mathrm{mod}14978\right)}}$ is obtained $r_i=r_5=8$ , $s_5=50$ , n is odd, i is odd.

From the above results we can see: $i=2$ , $3\times r_2^3=3993<14978$ , $5\times {13}^3<14978$ .

So the positive integer solution of the indefinite equation is:

$x=11,y=13.$

Example 3. Find the positive integer solution of $\text{20527956}=x^{\text{5}}+y^{\text{5}}$ .

Solving the congruence $z^5\equiv -1\left(\mathrm{mod}20527956\right)$ yields the following 5 positive integer solutions:

$3539303,6224291,6284051,17595395,20527955.$

$\overleftrightarrow{{\left(20527956,3539303\right)}_{{3639303}^5\equiv -1\left(\mathrm{mod}20527956\right)}}$ Giving:$r_i=r_4=7$ , $s_4=29$ , ${\text{29}}^{\text{5}}<20527956$ .

$\overleftrightarrow{{\left(\text{20527956,6224291}\right)}_{{6224291}^5\equiv -1\left(\mathrm{mod}20527956\right)}}$ Giving $r_i=r_9=13$ , $s_9>60$ , n is odd, i is odd.

$\overleftrightarrow{{\left(\text{20527956,6284051}\right)}_{62840515\equiv -1\left(\mathrm{mod}20527956\right)}}$ Giving $r_i=r_9=23$ , $s_9>60$ , n is odd, i is odd.

$\overleftrightarrow{{\left(\text{20527956,17595395}\right)}_{{17595395}^5\equiv -1\left(\mathrm{mod}20527956\right)}}$ Giving $r_i=r_2=29$ , $s_2=7$ , $7^5<20527956$ .

$\overleftrightarrow{{\left(\text{20527956,20527955}\right)}_{20527955\equiv -1\left(\mathrm{mod}20527956\right)}}$ Giving $r_i=r_1=1$ , $s_1=1$ , n is odd, i is odd.

From the above results we can see: $i=\text{4}$ , $s_4^5={29}^5<20527956$ .

So the positive integer solution of the indefinite equation is:

$x=7,y=29.$

From the above results we can see: $i=\text{2}$ , $s_2^5=7^5<20527956$ .

So the positive integer solution of the indefinite equation is:

$x=29,y=7.$

Example 4. Find the positive integer solution of $26067=x^3+7y^3$ .

Solving the congruence $7z^3\equiv -1\left(\mathrm{mod}26067\right)$ yields the following 3 positive integer solutions: 6890,19208,26036.

$\overleftrightarrow{{\left(26067,6890\right)}_{7\times {6890}^3\equiv -1\left(\mathrm{mod}26067\right)}}$ is obtained $r_i=r_8=10$ , $s_8=227$ , ${\text{227}}^{\text{3}}>26067$ .

$\overleftrightarrow{{\left(26067,19208\right)}_{7\times {19208}^3\equiv -1\left(\mathrm{mod}26067\right)}}$ is obtained $r_i=r_4=14$ , $r_i=r_4=14$ , ${\text{19}}^{\text{3}}<\text{26067}$ .

$\overleftrightarrow{{\left(26067,26036\right)}_{7\times {26036}^3\equiv -1\left(\mathrm{mod}26067\right)}}$ is obtained $r_i=r_3=4$ , $s_3=841$ , n is odd, i is odd.

From the above results we can see: $i=\text{4}$ , $\text{7}\times r_4^3=7\times {14}^3<26067$ , ${\text{19}}^{\text{3}}<26067$ .

So the positive integer solution of the indefinite equation is:

$x=19,y=14.$

Example 5.

Example 5. Find the positive integer solution of $59783703=5x^4+11y^4$ .

Solving the congruence $5z^3\equiv -11\left(\mathrm{mod}59783703\right)$ has no positive integer solution.

According to theorem 2: indefinite equations have no positive integer solution.

5. Conclusions

For the indefinite equation $m=x^2+y^2$ (m is a given positive integer), as long as $z^2\equiv -1\left(\mathrm{mod}m\right)$ has a solution, the positive integer solution can be obtained by the Euclidean algorithm.

For the indefinite equation $m=q{x}^n+p{y}^n$ ($n\ge 2,m,q,p$ are all given positive integer, $\left(q,p\right)=1$ ), it can be solve by solving the congruence $q{z}^n\equiv -p\left(\mathrm{mod}m\right)$ method to judge whether the equation has a positive integer solution, if $q{z}^n\equiv -p\left(\mathrm{mod}m\right)$ has no positive integer solution, then the equation has no positive Integer solution; if the congruence formula has solutions, it can be judged and solved according to the Euclidean algorithm given in this paper.

The above method is a general and effective method.

Conflicts of Interest

The author declares no conflicts of interest.

Conflicts of Interest

The author declares no conflicts of interest.

References

[1]	Ke, Z. and Sun, Q. (2011) Talk about Indefinite Equations. Harbin Institute of Technology Press.
[2]	Pan, C.D. and Pan, C.B. (2009) Elementary Number Theory. Beijing University Press, 279-280.
[3]	Vinogradov (2014) Fundamentals of Number Theory and Vinogradov. Harbin Institute of Technology Press, 43-45.
[4]	Ji, J. (2013) Number Theory and Application. Tsinghua University Press, 23.
[5]	Silverman, J.H. (2008) Introduction to Number Theory. Ministry of Machinery Industry Press, 127.