Conjecture re form x^2 + Mxy + y^2

[ramsey2879]

Conjecture: If x and y are coprime and M <> 2 then x^2 + Mxy +y^2 = p^2 has integral solutions only for p = a prime or for products of such primes. Also if M is positive then
both x and y are partial solutions for X^2 -MXY + Y^2 = p^2. Thus 3*3 +3*5 +5*5 = 49 and 9 - 3*8 + 8*8 and 25 - 5*8 + 84 also equal 49

 

[al-mahed]

x^2 +Mxy +y^2 == 0 mod n

for M<2, x^2 +Mxy +y^2 = (x+y)^2 - kxy, where M = 2-k

for M>2, x^2 +Mxy +y^2 = (x+y)^2 + kxy, where M = 2+k

$$(x+y)^2 == \pm kxy \ mod \ n$$

as n do not divide (x+y), then for euler

$$(x+y)^{\varphi(n)} == 1 \ mod \ n$$

supose n is composite ==> $$\varphi(n)} = 2^ah$$ such that a > 1 and h is odd ==>

==> $$\huge (x+y)^{2^{2^{a-1}h}} = (x+y)^{2^ah} = (x+y)^{\varphi(n)} == (\pm kxy)^{2^{a-1}h} == 1 \ mod \ n$$

call $$(\pm kxy)^{2^{a-1}} = w$$, and w is obviously positive, then

$$w^h == 1 \ mod \ n$$, an absurdum

**then n is prime**

 

[ramsey2879]

x^2 +Mxy +y^2 == 0 mod n

for M<2, x^2 +Mxy +y^2 = (x+y)^2 - kxy, where M = 2-k

for M>2, x^2 +Mxy +y^2 = (x+y)^2 + kxy, where M = 2+k

$$(x+y)^2 == \pm kxy \ mod \ n$$

as n do not divide (x+y), then for euler

$$(x+y)^{\varphi(n)} == 1 \ mod \ n$$

supose n is composite ==> $$\varphi(n)} = 2^ah$$ such that a > 1 and h is odd ==>

==> $$\huge (x+y)^{2^{2^{a-1}h}} = (x+y)^{2^ah} = (x+y)^{\varphi(n)} == (\pm kxy)^{2^{a-1}h} == 1 \ mod \ n$$

call $$(\pm kxy)^{2^{a-1}} = w$$, and w is obviously positive, then

$$w^h == 1 \ mod \ n$$, an absurdum

**then n is prime**

But for n = 13*7 and M = 1 there is a solution, , i.e. x = 39, y = 65, how does that agree with your conclusion that n must be prime?

 

[al-mahed]

Nevermind, I made a mistake in the proof, the conclusion is wrong, I tried to repair the proof without success.

Please, define a little more clear your conjecture, what you mean saying "integral solutions"?

 

[ramsey2879]

Conjecture: If x and y are coprime and M <> 2 then x^2 + Mxy +y^2 = p^2 has integral solutions only for p = a prime or for products of such primes. Also if M is positive then
both x and y are partial solutions for X^2 -MXY + Y^2 = p^2. Thus 3*3 +3*5 +5*5 = 49 and 9 - 3*8 + 8*8 and 25 - 5*8 + 84 also equal 49

Another example
7*7 + 7*8 + 8*8 = 13^2

19^2 + 19*80 + 80^2 = 49^2*13^2 = (7*13)^2

Please disreegard the solution in my last post since 39 and 65 are not coprime.
By integral solutions, I mean coprime positive integers.

 

[al-mahed]

in fact n = 13*7*91, your conjecture is about p and p^2 only? or what? every composite number? I did not follow this part.

 

[al-mahed]

ok, so the conjeture is: for x and y coprime, the expression is equal to some power of a prime number OR some power or a semi-prime number (a product with no more than 2 different factors)?

 

[al-mahed]

if your conjecture is about only squares, then we can use the fact that a square is a number of the form 8n+1 where n is a triangular number

 

[Ynaught?]

How about:

Iff M=1 and (x,y,p) are positive coprime integers, then p = a prime of the form 6n+1, or a multiple thereof, or a product of two or more primes thereof.

Similar to Pythagorean Triples where the equation is x^2+y^2=p^2 and p = a prime of the form 4n+1...

Added a bit later... Alternatively, for every prime p, of the form 6n+1, there is one and only one pair of positive integers (x,y) that satisfy the equation x^2+xy+y^2=p^2 (where x and y are not equal and are interchangeable).

 

[ramsey2879]

How about:

Iff M=1 and (x,y,p) are positive coprime integers, then p = a prime of the form 6n+1, or a multiple thereof, or a product of two or more primes thereof.

Similar to Pythagorean Triples where the equation is x^2+y^2=p^2 and p = a prime of the form 4n+1...

Added a bit later... Alternatively, for every prime p, of the form 6n+1, there is one and only one pair of positive integers (x,y) that satisfy the equation x^2+xy+y^2=p^2 (where x and y are not equal and are interchangeable).

Whether a prime can be expressed in the form of x^2 + Mxy + y^2 where x and y are coprime depends upon the value of M. If M = 2 all integers n have upto (n-1)/2 distinct solutions But, if M = 1 and [tex] n = p_{a1}^{i1}*p_{a2}^{i2}*..p_{ah}^{ih} where p are primes, believe that there are k and only k distinct solutions where x and y are positive coprime integers (k = the sum of the powers {i1,i2,...ih} or = the number of prime factors but I don't have my work before me and I forgot) if and only if there exists solutions at all. But for M = 1 certain primes such as 3,5,11... and their products can not be expressed in this form at all. For M > 2 if x,y is a solution for n then y and (My -x) is also a solution. Note that the first few solutions for x^2 + Mxy + y^2 = n^2 occur only for n = a prime p for M > 2 since my conjecture is that if n is a product of primes then each of the primes that divide n and the the powers and products of those primes can also be expressed in the form x^2 + Mxy + y^2 for that M.

 

[ramsey2879]

Just calculated a interesting result
If $$n = a^2 + Mab + b^2$$,$$c = b^2-a^2$$ and $$d=2ab -Mb^2$$

then $$n^2 = c^2 -Mcd + d^2$$

also the polarity of any 2 of M, c and d can be reversed since -1 * -1 = 1

 

[robert Ihnot]

The above formula doesn't seem to work. Let a=b=M=1. Give n=3, c=0, d=1. Then it is not true: 3^2=0-0+1^2.

In the case of a^2+b^2+ab, we can look at this in the form: $$\frac{a^3-b^3}{a-b}.$$ So for a not equal to b, the case for 3, we have the form: $$a^3\equiv{b^3}\bmod{p}$$ where the two integers are not the same. This shows that 3 is a divisor of p-1, and therefore p=3k+1. Since k is even, the form is 6k+1.

This then includes the primes 7, 13, 19, 31...As suggested by Ynaugh?

Whether there is a strictly positive integral form for the square of a prime is another matter. As ramsey2879 shows in his original entry: "Thus 3*3 +3*5 +5*5 = 49 and 9 - 3*8 + 8*8 and 25 - 5*8 + 84 also equal 49."

So here we have the number 7, of the form 3k+1, and 7=2^2+1^2+2x1, and so there is an all positve form for the square.

Also, I see that 13=3^2+1^1+3, and 13^2 = 8^2+7^2+56. Now, 19=3^2+2^2+6; 19^2=16^2+5^2+80.
31=5^2+5+1; 31^2=24^2+11^2+264.

There is, however, a key to this matter: We can decompose $$a^2+b^2+ab = (a-b\omega)(a-b\omega^2)$$, where $$\omega =\frac{-1+\sqrt-3}{2}$$

For example: finding the case of 37 = 4^2+3^2+12. We decompose this into:$$(4-3\omega)(4-3\omega^2)$$ then we square the first factor and simplify using the fact: $$1+\omega+\omega^2=0$$. We then arrive at the first factor for the square is: $$(7-33\omega)$$

The square solution then is: $$37^2=33^2+7^2+33x7$$

The use of this method then makes it clear, anytime we can find the above form for the prime, of the form 6k+1, we can build on this to any higher power as well as to any product of such primes. For example: $$43^3=126^2+197^2+126x197.$$

However, if we are to have an all positive form then a and b must be of the different signs in the decomposition. Three is a problem in itself, $$3=(1-\omega)(1-\omega^2)$$, and there is no good form for 9, trivally, 3^2=3^2+3^3-3^2. Using the above ideas to get the form 3 times 37^2, we arrive at $$-26-63\omega$$, this produces $$3x37^2=26^2+73^2-26x73$$

 

[Ynaught?]

Hey Robert Ihnot, I am a bit slow... Can you expand on this?

There is, however, a key to this matter: We can decompose $$a^2+b^2+ab = (a-b\omega)(a-b\omega^2)$$, where $$\omega =\frac{-1+\sqrt-3}{2}$$

Thanks!

 

[robert Ihnot]

O.K., actually I thought you were way ahead of me on this!

Omega is the cube root of 1, which can be gotten from Euler's formula, here we have:
cos(120) +isin(120). In an equation such as X^3-1 = 0. The second quadratic term, x,which is the sum of the roots, goes out. That is cos(120)+isin(120) +cos(240)+isin(240) =-1, so adding the third root cos(360)+isin(360) becomes just 0. (This may not be your question, but as a general rule the sum of the nth roots of unity is zero.)

Multiply together$$(a-b\omega^2)a-(a-b\omega^2)b\omega = a^2 +-ab\omega^2-ab\omega+b^2.$$ Now for the terms: $$-ab\omega-ab\omega^2=ab$$ So that we are left with $$a^2+ab+b^2$$ Thus what has happened has been a factoring over the complex numbers.

Another case of this is over the Gaussian integers we have:$$X^2+Y^2=(X+iY)(X-iY)$$

 

[ramsey2879]

The above formula doesn't seem to work. Let a=b=M=1. Give n=3, c=0, d=1. Then it is not true: 3^2=0-0+1^2.

In the case of a^2+b^2+ab, we can look at this in the form: $$\frac{a^3-b^3}{a-b}.$$ So for a not equal to b, the case for 3, we have the form: $$a^3\equiv{b^3}\bmod{p}$$ where the two integers are not the same. This shows that 3 is a divisor of p-1, and therefore p=3k+1. Since k is even, the form is 6k+1.

a and b are coprime and also can not be both equal to 1, Question is 1 coprime to 1? Origionally I did not consider this exception. Thanks for pointing it out.

 

[Ynaught?]

O.K., actually I thought you were way ahead of me on this!

LOL I am just trying to understand a picture and I did not mean to hi-jack the thread...

Omega is the cube root of 1, which can be gotten from Euler's formula, here we have:
cos(120) +isin(120). In an equation such as X^3-1 = 0. The second quadratic term, x,which is the sum of the roots, goes out. That is cos(120)+isin(120) +cos(240)+isin(240) =-1, so adding the third root cos(360)+isin(360) becomes just 0. (This may not be your question, but as a general rule the sum of the nth roots of unity is zero.)

Thank you. That helped.

 

[robert Ihnot]

1s are coprime? Well, the important matter is that if p, a prime, =a^2+b^2+ab, it is obvious that a and b could not have a common factor greater than 1. And the case for 3 is that a=b=1.

 

[ramsey2879]

1s are coprime? Well, the important matter is that if p, a prime, =a^2+b^2+ab, it is obvious that a and b could not have a common factor greater than 1. And the case for 3 is that a=b=1.

Yes but c^2 -cd + d^2 <> 9 for c and d as integers. Also, the important matter is that a <> b. How about n is not prime if the greatest commom divisor of c and d <> 1 since the greatest common divisor of c and d divides n If gcd(c,d) = 1 then n^2 = c^2 -Mcd + d^2?

 

[robert Ihnot]

You can work on that!

 

[ramsey2879]

The above formula doesn't seem to work. Let a=b=M=1. Give n=3, c=0, d=1. Then it is not true: 3^2=0-0+1^2.

In the case of a^2+b^2+ab, we can look at this in the form: $$\frac{a^3-b^3}{a-b}.$$ So for a not equal to b, the case for 3, we have the form: $$a^3\equiv{b^3}\bmod{p}$$ where the two integers are not the same. This shows that 3 is a divisor of p-1, and therefore p=3k+1. Since k is even, the form is 6k+1.

This then includes the primes 7, 13, 19, 31...As suggested by Ynaugh?

Whether there is a strictly positive integral form for the square of a prime is another matter. As ramsey2879 shows in his original entry: "Thus 3*3 +3*5 +5*5 = 49 and 9 - 3*8 + 8*8 and 25 - 5*8 + 84 also equal 49."

So here we have the number 7, of the form 3k+1, and 7=2^2+1^2+2x1, and so there is an all positve form for the square.

Also, I see that 13=3^2+1^1+3, and 13^2 = 8^2+7^2+56. Now, 19=3^2+2^2+6; 19^2=16^2+5^2+80.
31=5^2+5+1; 31^2=24^2+11^2+264.

There is, however, a key to this matter: We can decompose $$a^2+b^2+ab = (a-b\omega)(a-b\omega^2)$$, where $$\omega =\frac{-1+\sqrt-3}{2}$$

For example: finding the case of 37 = 4^2+3^2+12. We decompose this into:$$(4-3\omega)(4-3\omega^2)$$ then we square the first factor and simplify using the fact: $$1+\omega+\omega^2=0$$. We then arrive at the first factor for the square is: $$(7-33\omega)$$

The square solution then is: $$37^2=33^2+7^2+33x7$$

The use of this method then makes it clear, anytime we can find the above form for the prime, of the form 6k+1, we can build on this to any higher power as well as to any product of such primes. For example: $$43^3=126^2+197^2+126x197.$$

However, if we are to have an all positive form then a and b must be of the different signs in the decomposition. Three is a problem in itself, $$3=(1-\omega)(1-\omega^2)$$, and there is no good form for 9, trivally, 3^2=3^2+3^3-3^2. Using the above ideas to get the form 3 times 37^2, we arrive at $$-26-63\omega$$, this produces $$3x37^2=26^2+73^2-26x73$$

Now that I had more time to consider this I did make a typo in the formula for d it should have been 2ab +mb^2 so my form reduces to 0^2 -0*3 + 3^2 = 3^2

Note That If you square $$a-b\omega$$ you get $$a^2 - 2ab\omega + b^2\omega^2 = a^2-b^2 - (2ab+b^2)\omega$$ so c = a^2-b^2 and d = (2ab+b^2).

Thus c^2 +cd + d^2 = [-c]^2 -[-c]d + d^2 = n^2 which is my result.

Also this proves that gcd(c,d) divides n since each term on the left of my equation is divisable by the square thereof.

A interesting portion of my conjecture is that if n is composite then each factor of n must be of the form a^2 + Mab + b^2 but as you said in the last post M = 13 is a problem since a = 0 and b = 3 is a trival result, which I think is removed by the requirement that gcd(c,d) must equal 1. However, your showing that $$3x37^2=26^2+73^2-26x73$$ needs to be considered. There $$c = 73^2 - 26^2 = 4653$$ Since 3|4653 then the gcd(c,d) at least equals 3. Thus this does not contradict my conjecture that all n of the general form where gcd(c,d) = 1 can be expressed as a product of primes each of which is of the form where the gcd(c,d) = 1.

PS Do you have any suggestion of how to extend this to the general form where |M|>2?

If my conjecture is true this result can find large primes by keeping a = 1, b = 2 and choosing a large M not divisible by 3 such that the gcd(c,d) = 1.

 

[ramsey2879]

If my conjecture is true this result can find large primes by keeping a = 1, b = 2 and choosing a large M not divisible by 3 such that the gcd(c,d) = 1.

I just realized that if a = 1 and b = 2, gcd(c,d) = gcd(2ab + Mb^2,b^2-a^2) which equals gcd(-3,4+4M) = 1 for M = 0 or 1 mod 3, but 5 + 2M is not prime for all M = 0 or 1 mod 3. I need to consider this further.

 

[ramsey2879]

hj

Now that I had more time to consider this I did make a typo in the formula for d it should have been 2ab +mb^2 so my form reduces to 0^2 -0*3 + 3^2 = 3^2

Note That If you square $$a-b\omega$$ you get $$a^2 - 2ab\omega + b^2\omega^2 = a^2-b^2 - (2ab+b^2)\omega$$ so c = a^2-b^2 and d = (2ab+b^2).

Thus c^2 +cd + d^2 = [-c]^2 -[-c]d + d^2 = n^2 which is my result.

Also this proves that gcd(c,d) divides n since each term on the left of my equation is divisable by the square thereof.

...
If my conjecture is true this result can find large primes by keeping a = 1, b = 2 and choosing a large M not divisible by 3 such that the gcd(c,d) = 1.

I found that if we let $$a = 2$$ and $$b = 1$$ then any odd number greater than 5 can be expressed in the form $$N = 5 + 2M = a^2 + Mab + b^2$$ and so the square is of the form $$N^2 = c^2 + cdM + d^2$$ where $$c = 3$$ and $$d = 4 + M$$. Of course $$M = (N -5)/2$$.

Now If 3|N then 3|d and gcd(c,d) $$\neq$$ 1 but if 3 does not divide N the gcd(c,d) = 1. I considered the relation between c,d and the factors of $$N$$.
THEOREM: If and only if $$R$$ is a factor of N then $$gcd(c+2t,d+t) = gcd(3 + 2t,(N-5)/2 + 4 + t) = R$$ for $$t = (R-3)/2$$
Proof: For $$t equals (R-3)/2$$, $$c + 2t = R$$ and $$d = (N + R)/2and$$gcd(a,n + a) = a[/tex] only if a|n.

thus 35 = 5 + 2*15, c = 3, d = 15+4 = 19

t c+2t d + t gcd(c+2t,d+t)
0 3 19 1
1 5 20 5
2 7 21 7
3 9 22 1
4 11 23 1
5 13 24 1
6 15 25 5
7 17 26 1
8 19 27 1
9 21 28 7
10 23 29 1
..
16 35 35 35

As seen the algorithm starts with the gcd of a numbers on the order of N/2 and 3 and proceeds in an orderly fashion to find the divisors of N. Is this useful or is it too much effort to be useful?