5 ms·

Should be: 88 percent of all integers have a PRIME factor under 100 All integers have a factor under 100, which is 1.

by igitur 10y ago

mrkgnao 10y ago
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. https://en.wikipedia.org/wiki/Prime_element https://en.wikipedia.org/wiki/Prime_element [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: https://en.wikipedia.org/wiki/Euclidean_domain https://en.wikipedia.org/wiki/Euclidean_domain [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 ;) https://en.wikipedia.org/wiki/Splitting_of_prime_ideals_in_Galois_extensions#Example_.E2.80.94_the_Gaussian_integers https://en.wikipedia.org/wiki/Splitting_of_prime_ideals_in_G... 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_two_squares https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_...
- jessaustin 10y ago
  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.
  - mrkgnao 10y ago
    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/ 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. :)
E6300 10y ago
> 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).
- pherq 10y ago
  I'm pretty sure the standard definition of primes permits only natural numbers.
  - jiiam 10y ago
    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"
    - bikenaga 10y ago
      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.

Should be: 88 percent of all integers have a PRIME factor under 100 All integers have a factor under 100, which is 1.

by igitur 10y ago

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. https://en.wikipedia.org/wiki/Prime_element https://en.wikipedia.org/wiki/Prime_element [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: https://en.wikipedia.org/wiki/Euclidean_domain https://en.wikipedia.org/wiki/Euclidean_domain [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 ;) https://en.wikipedia.org/wiki/Splitting_of_prime_ideals_in_Galois_extensions#Example_.E2.80.94_the_Gaussian_integers https://en.wikipedia.org/wiki/Splitting_of_prime_ideals_in_G... 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_two_squares https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_...

jessaustin 10y ago
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.
- mrkgnao 10y ago
  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/ 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. :)

E6300 10y ago

> 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).

pherq 10y ago
I'm pretty sure the standard definition of primes permits only natural numbers.
- jiiam 10y ago
  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"
  - bikenaga 10y ago
    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.