2

While I am reading in The Higher Arithmetic , I found this example

the proof that the factorization is unique is not so immediate. The following illustration, given by Hilbert, explains why these two propositions are on such a different footing from one another.

The definitions of factors and primes involve solely the operation of multiplication, and have no reference to that of addition. Now consider what happens when the same definitions are applied to a system of numbers which can be multiplied together, but which cannot be added or subtracted without going outside the system. Take the system of numbers

1, 5, 9, 13, 17, 21, 25, 29, . . . ,

comprising all numbers of the form 4x + 1. The product of any two such numbers is again a number of the same kind. Let us define a ‘pseudo-prime’ to be a number in this system (other than 1) which is not properly factoriz- able in this system. The numbers 5, 9, 13, 17, 21 are all pseudo-primes, and the first number in the series which is not a pseudo-prime is 25. It is true that every number in the system is either a pseudo-prime or can be factorized into pseudo-primes, and this can be proved in just the same way as before. But it is not true that the factorization is unique; for example, the number 693 can be factorized both as 9×77 and as 21×33, and the four numbers 9, 21, 33, 77 are all pseudo-primes. my questions are:

-Which branch of mathematics does study something like what Hilbert did in this example, the dependence of proof?

-any good books on that field?

Community
  • 1
SomeOne
  • 917
  • 1
    The properties used are elementary properties of the binary quadratic form $x^2 + y^2.$ Along with that would be use of congruences (all these numbers satisfy $n \equiv 1 \pmod 4.$) If you also know quadratic reciprocity, you are all set. The numbers $6x+1$ should do roughly the same things. A more direct relation to a form is the numbers $3x+1.$ – Will Jagy Sep 18 '13 at 21:26
  • Yes, with all $3x+1,$ we have pseudo primes $10, 22, 34, 55, 85, 187, $ while $$ 1870 = 10 \cdot 187 = 22 \cdot 85 = 34 \cdot 55. $$ – Will Jagy Sep 18 '13 at 21:30

1 Answers1

3

To show the relationship with quadratic residues a little better, take all $7x+1,2,4$ that is $$ 1,2,4,8,9 ,11,15,16,18,22,23,25,29,30,32,36,37,39, \ldots$$

We find pseudo primes $$ 15, 39, 51,65,85, 221. $$ Then $$ 3315 = 15 \cdot 221 = 39 \cdot 85 = 51 \cdot 65. $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Back from errand. There is no real need to have a pattern to create one of these multiplicatively closed sets, while several simple patterns work. You can have $nx \pm 1,$ for example. However, if you take $4x \pm 1,$ you get all the odd numbers, and the pseudoprimes are genuine primes. So you are back to unique factorization. Similar for $6x \pm 1,$ all odd numbers not divisible by $3.$ $5x \pm 1$ works, those are quadratic residues $\pmod 5.$

I'm having some trouble doing cubic residues.

EDIIITTT: cubic residues work, there are just restrictions because now the cubic non-residues have two distinct cosets. So, for $7x \pm 1,$ we get non-unique pseudoprime factorization in $$ 330= 6 \cdot 55 = 15 \cdot 22 $$

Will Jagy
  • 139,541