Primes With Complex Factors

Matthew Seaman m.seaman at infracaninophile.co.uk
Sun May 11 21:59:56 BST 2008


This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enig8F1C36FC832A59C8B9D24FC3
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable

Lee Brotherston wrote:
> On Sun, May 11, 2008 at 08:12:07PM +0100, Frank Shute wrote:

>> I'd like to see some higher primes than 2 factored with complex
>> numbers. Two's a bit of a special case (only even prime) and small.
>=20
> Yeah - it would be interesting.

Well, if you're going to multiply two complex numbers and end up with
a positive real prime number as a result, then those numbers must have
equal and opposite phase -- ie. they are complex conjugate to within a
scale factor.

In the general case, we want:

   (a + ib)(c + id) =3D p     [1]

where p is prime.

   ac - bd + i(ad + bc) =3D p

The imaginary part of p is zero, so:

   ad + bc =3D 0

   a/b =3D -c/d=20

Which is the phase angle requirement above.

This implies that we can rewrite [1] as:

  (a + ib)(c + id) =3D R(a + ib)(a - ib) =3D p

where R is just a scale factor.  This leads to:

  R(a^2 + b^2) =3D p

If we now require all the entities a, b, c, d to be integers then R must
be identically 1, or p could not be prime.

So in order for a prime number to have this sort of complex factorization=

it must be equal to the sum of two squares.  There are a number of result=
s
from just the first 10 integers above zero:

     1    2    3    4    5    6    7    8    9   10
  1  2*   5*  10   17   26   37*  50   65   82  101*
  2       8   13*  20   29*  40   53*  68   85  104
  3           18   25   34   45   58   73*  90  109
  4                32   41*  52   65   80   97* 116=20
  5                     50   61*  74   89* 106  125
  6                          72   85  100  117  136
  7                               98  113* 130  149*
  8                                   128  145  164=20
  9                                        162  181*
 10                                             200

	Cheers,

	Matthew

--=20
Dr Matthew J Seaman MA, D.Phil.                   7 Priory Courtyard
                                                  Flat 3
PGP: http://www.infracaninophile.co.uk/pgpkey     Ramsgate
                                                  Kent, CT11 9PW


--------------enig8F1C36FC832A59C8B9D24FC3
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (FreeBSD)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEAREIAAYFAkgnXlIACgkQ8Mjk52CukIzvxACfe8BFoJGmv51gvIhsZ0AZwHse
gXkAn0TcglZsYNxK5vZ5/velwfZTWKEe
=EyaQ
-----END PGP SIGNATURE-----

--------------enig8F1C36FC832A59C8B9D24FC3--




More information about the Ukfreebsd mailing list