Hacker News new | past | comments | ask | show | jobs | submit login

Should be:

88 percent of all integers have a PRIME factor under 100

All integers have a factor under 100, which is 1.

The concept of factorization, properly defined, usually excludes "units", that is, numbers with an inverse. So 1 is a unit, since we can solve

  1x = 1 
by letting x = 1. -1 is a unit too, since (-1)x = 1 is also solvable.

Factorization is then defined "upto units and reordering", so, for instance,

  6 = 2 * 3 = (-2) * (-3) = 3 * 2 = (-3) * (-2)
are all considered the same factorization.

Why might this be useful? Sometimes, number systems ("rings") we care about might have more units, and in order for there to be a sensible theory of factorization[1], we have to take these things into account. Not all rings are as nice as Z[2].

For instance, allow me to go off on a tangent: consider the set of all numbers of the form

  a + ib (a, b integers)
called the Gaussian integers (written Z[i]). One can show that the units here are 1, -1, and also two new ones: i and -i. Studying factorization in this ring -- what numbers can we factorize further now? -- is very interesting. It turns out that not all of our usual prime numbers "remain prime":

   2 = 1  + 1 = 1 -  i^2   = (1 + i)^2
   3 = 3 
   5 = 1  + 4 = 1 - (2i)^2 = (1 + 2i)(1 - 2i)
   7 = 7
  11 = 11
  13 = 4  + 9 = 4 - (3i)^2 = (2 + 3i)(2 - 3i)
The key to this puzzle is to notice that the primes that "split"[3] all leave a remainder of 1 modulo 4. It is a beautiful fact that the converse also holds: if

  p = 1 (mod 4) 
then it must factor in Z[i], and, further, it always factors as

  p = (a + ib)(a - ib) = a^2 + b^2
(And, of course, if we have p = a^2 + b^2, it can be factored just like we did above.) In other words,

  Theorem[4] (Fermat, sometimes called the "Christmas theorem"). 
  The primes that can be written as a sum of two squares are exactly those congruent to 1 mod 4.
Neither the question (which primes can be written as a sum of two squares) nor the answer (those congruent to 1 mod 4) involve any of the machinery we used in getting from one to the other. :)

PS. Yes, I may or may not have ignored the case of 2 above. Tons of theorems in number theory are stated for "odd primes". 2 is, after all, the oddest prime.


[1]: e.g. it turns out that "p is prime", defined as

  p | ab implies p | a or p | b
and "p is irreducible" (i.e. not factorizable in any sensible way), defined as

  p = ab implies either a or b is a unit
are not equivalent! One direction always holds, but the other doesn't come for free.


[2]: Each step up the ladder of class inclusions adds some nice property that makes life easier, but diminishes the power of the theorems one proves. (Euclidean domains are almost perfect in that sense!) Behold, a bestiary most vile:


[3]: Notice that 2 factorizes as a power, not as a product of distinct factors. This is technically "ramification", not "splitting" (that term is reserved for the distinct-factors case). The following Wikipedia page treats the entire content of this post far better, and has links to the "real" algebraic number theory pages ;)


The numbers that don't factorize at all are said to remain "inert". (And there's something related called an "inertia group" that disappointingly has little to do with mechanics.)

[4]: https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_...

What a beautiful response to a completely unnecessary comment! Thanks.

School has forced me to take a break (thankfully coming to an end now) from learning math for the past few months, so throwing walls of text at the gracious HN crowd simultaneously makes for good practice and expository-itch-scratching. You're welcome.

Your factorization of 2 is wrong.

(1 + i)² = 2i

2 = (1 + i)(1 - i)

I don't think that invalidates anything else you have here, much of which is interesting.

The factorization of 2 is fine -- factorizations are equivalent if they're off by a unit, and i is a unit.

By the same token, 1+i and 1-i are essentially the same prime, since you can multiply one by a unit to get the other. That's how we can get away with saying 2 is a power.

edit: Just noticed the sibling comment by mrkgnao, which is a very good overview of some of the technical nitty-gritty that goes into this.

Apologies. I was remembering more than I was thinking: you are right in that the relation doesn't hold at the level of elements[0]. The correct statement is

  (2) = (1+i)^2
where (2) and (1+i) represent the ideals generated by 2 and 1+i respectively. Officially, an ideal of a ring R is a subset I of R which is closed under addition and under and multiplication by elements of R:

  i, j ∈ I implies  i + j ∈ I
  i    ∈ I implies     ri ∈ I for all r ∈ R
For our purposes, a simpler case -- that of principal ideals -- suffices, and that's what I'll discuss in the rest of this comment.

The ideal generated by an element a of a ring R, usually denoted (a) or aR, is essentially the subset of all multiples of a in R. For instance, over the integers, we have ideals like

  (2) = {...,  -4, -2, 0, 2, 4,  ...} 
  (3) = {...,  -6, -3, 0, 3, 6,  ...}
  (4) = {...,  -8, -4, 0, 4, 8,  ...}
  (6) = {..., -12, -6, 0, 6, 12, ...}
One can also define the ideal generated by the elements a,b,c,... of R:

  (a,b,c,...) = {aa' + bb' + cc' + ... : a',b',c' ∈ R}
i.e. the "linear combinations" of a, b, c, and so on.

Here are a few things you might like to verify (i.e. just nod along) about some ideals of Z, to get familiar with the notation:

  (1) = Z (i.e. all the integers)
  (2) = (-2)
  (6) = (2) ∩ (3) 
  15Z =  3Z ∩ 5Z
where ∩ is the intersection of the two sets, or the set of common elements. ("Fact": The intersection of two ideals is also an ideal.)

In general, if you have an ideal of the form (a), then we always have

  (a) = (ua) for all units u
Write G (for Gauss?) for Z[i]. In G, the previous statement means that (2) = (2i). To check this, note that we have

      x ∈ (2) 
  iff x =  2y            for some y
  iff x = (2i)(-yi)
  iff x ∈ (2i)
so all elements of (2) are in (2i), and vice versa.

Now one defines the product of ideals: given ideals I and J in some ring R,

  IJ = ideal generated by the elements {ij : i ∈ I, j ∈ J}
In our case, if I = (a) and J = (b), IJ is just (ab). Question: what's the relation between (ab) and (a) ∩ (b)?

For instance, you can verify that

  (2)(3) = (6)
and, to bring us back to our original point,

  (1+i)(1-i) = (2i) = (2) = (1+i)^2
where all the products are ideal products.


There is a very incomplete treatment at [1] (with a bit of the LaTeX broken) that is meant to provide background for a sequence of posts on algebraic geometry -- it's been suspended for a while, but I'm going to look over a couple of drafts this week!

[1]: https://mrkgnao.github.io/prime-ideals/

[0]: As always in math: if you can't prove it, just add a few adjectives or simply change the language. Facts arrived at by alternative definitions, if you will. :)

> 88 percent of all integers have a PRIME factor under 100

In fact, all integers have at least one prime factor under 100, since is_prime(n) implies is_prime(-n).

I'm pretty sure the standard definition of primes permits only natural numbers.

Nope, we usually mean both negative and positive when talking about prime integers. Still, the question on hand is clearly restricted to the positive case, otherwise it would be trivial.

EDIT: better yet, the proper formulation with regard to all integers would be "integers having a prime factor p such that |p| < 100"

Prime elements in a ring (usually an integral domain) are elements which satisfy Euclid's lemma (so p is a prime element if p | a b implies p | a or p | b), so the prime elements in the ring of integers are 2, -2, 3, -3, and so on. But if someone refers to prime numbers, they mean 2, 3, 5, ... - it's the standard definition. In fact, if I meant to include both positive and negative elements in the context of the integers, I would go out of my way to say so to avoid confusion! I think the key is the use of the word "number" as opposed to "element" (say).

I think the terminology is a convenience - so many results pertain to 2, 3, 5, ... that it's easier to let "prime numbers" refer to them, rather than to have to qualify everything by saying "positive primes" or taking absolute values.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact