Date: Wed, 18 Jan 95 14:55:17 CST
From: rusin (Dave Rusin)
To: [permission pending]
Subject: Re: Diophintine Equations
Newsgroups: sci.math

The important thing to realize is that the equation you're trying to
solve may be written N(x+ysqrt(D))=b, where  N  is the norm mapping.
You might think of it as being just N(x+y sqrt(D)) = x^2-D y^2, but what
it really is, is  N(u)=u.ubar, where  u is any element of the ring
Q[sqrt(D)] and ubar is the conjugate of  u  (the "bar" of sqrt(D) is
-sqrt(D).) This shows that  N  is multiplicative: N(uv)=N(u)N(v). In
particular, if N(v)=1 and  u is one solution to  N(u)=b,  then  u.v
is another solution. Therefore, you only need to get one solution to
get infinitely many. 

The question of which elements  b  can be written as a norm at all is
more subtle. It can only be done if the ideal  (b)  factors as the product
of two conjugate ideals in the larger ring, and if those ideals are
principal. Just how  (b) factors depends on how the prime divisors of  b
factor in the larger ring; whether the ideals are principal depends on
the nature of the class group for this extension. I'm guessing that this
whole paragraph looks like babble to you, but at least you know what
you're up against. (Certainly it gives you the hint that if you can solve
N(u)=p  for each prime divisor  p  of  b, then you can solve N(u)=b;
unfortunately the converse is not true.)

I believe it's true that for sufficiently small numbers  b, the
equation  N(u)=b  is solvable iff  x^2-D y^2=b for some approximation
x/y of sqrt(D) which occurs before you have found the fundamental solution
of x^2-Dy^2=1, so that the problem is decidable and reasonably efficient.
But I can't even remember how small is "sufficiently small" (less than D,
maybe?), so you'd best not quote me on that.

dave

==============================================================================

From: [permission pending]
To: rusin@math.niu.edu
Date:          Sat, 21 Jan 1995 13:32:17 PST8PDT
Subject:       Re: Diophintine Equations

> The important thing to realize is that the equation you're trying 
> to solve may be written N(x+ysqrt(D))=b, where N is the norm
> mapping. You might think of it as being just N(x+y sqrt(D) = x^2 

What is a "norm mapping"?

[Deleted and Re-arranged]
> ... I'm guessing that this whole paragraph look like babble to
> you, but at least you know what you're up against.
> (Certainly it gives you a hint that if you can solve N(u)=p
> for each prime divisor p of b, then you can solve N(u)=b;
> unfortunately the converse if not true.)

I gather then that factoring "b" into its prime factors will generate 
some magical "rings". From these rings, the original equation can be 
solved. (If I keep re-reading your posting, hopefully the "babble" 
will make sense :-))

[Re-arranged]
> -Dy^2, but what it really is, is N(u)=u.ubar, where u is any 
> element of the ring Q[sqrt(D)] and ubar is the conjugate of u (the
> "bar" of sqrt(D) is -sqrt(D).) This shows that N is multiplicative:
> N(uv)=N(u)N(v). In particular, if N(v)=1 and u is one solution to
> N(u)=b, the u.v is another solution. Therefore, you only need
> to get one solution to get infinitely many.

This sparks an interesting thought. If I could generate *any*
solution to the equation x^2 - Dy^2 = b, is it possible to locate the 
base solution to the equation?

Regards,
[sig deleted]

==============================================================================

Date: Mon, 23 Jan 95 12:48:38 CST
From: rusin (Dave Rusin)
To: [permission pending]
Subject: Re: Diophintine Equations

You wrote:
>> The important thing to realize is that the equation you're trying 
>> to solve may be written N(x+ysqrt(D))=b, where N is the norm
>> mapping. You might think of it as being just N(x+y sqrt(D) = x^2 
>What is a "norm mapping"?
You need to find a book on algebraic number theory, in which you'll 
find this kind of connection spelled out as an example at some point.
Briefly, one looks at rings (sets in which an addition and multiplication
are defined) which contain the integers, such as the Gaussian integers
({a+bi: a, b integers}, where i=sqrt(-1).) The Norm is a function which
takes in elements of the larger ring and spits out integers. It has
the property that  N(xy)=N(x)N(y) for any  x  and  y. This is what turns
the Diophantine equation into a study with a little more (multiplicative)
structure.

>[Deleted and Re-arranged]
>> ... I'm guessing that this whole paragraph look like babble to
>> you, but at least you know what you're up against.
>> (Certainly it gives you a hint that if you can solve N(u)=p
>> for each prime divisor p of b, then you can solve N(u)=b;
>> unfortunately the converse if not true.)
>I gather then that factoring "b" into its prime factors will generate 
>some magical "rings". From these rings, the original equation can be 
>solved. (If I keep re-reading your posting, hopefully the "babble" 
>will make sense :-))
I'm not sure how you're using the word "ring". My post will probably not
make sense in and of itself (you have to remember that when I respond to 
you in the first place I have no idea how much formal training you've
had in this or any other direction).

You may wish to look up references to an analogous question: which
integers can be expressed as a sum of two squares? By leaning on the
Norm map for Gaussian integers, one can show the answer is: N=x^2+y^2
for some  x  and  y  if and only if  N  has no prime factors of the
form  p=4n+3.  (An interesting aside: EVERY integer can be written as
a sum of 4 squares. You need to pass from complex numbers to the 
quaternions to get this.)

>> N(uv)=N(u)N(v). In particular, if N(v)=1 and u is one solution to
>> N(u)=b, the u.v is another solution. Therefore, you only need
>> to get one solution to get infinitely many.
>This sparks an interesting thought. If I could generate *any*
>solution to the equation x^2 - Dy^2 = b, is it possible to locate the 
>base solution to the equation?
Well, I'm not sure what the "base" solution is, but I guess you mean the
one which is smallest by some measure. It is true that from any one
solution you can generate all others if you know the fundamental unit, 
that is, the "smallest" solution to x^2-Dy^2=1. I suppose you could
find a few solutions to x^2-Dy^2=b this way (once you had one, of course)
and then prove that all the other solutions are "larger". I'd have
to work this out, but I think it can be done.

good luck
dave