# Analogy between linear basis and prime factoring

I recall learning that we can define linear systems such that any vector in the system can be represented as a weighted sum of basis vectors, as long as we have 'suitable' definitions for addition and multiplication operators (i.e. fulfilling certain properties.) This turned out to be extremely useful, as we could prove general things about linear operations over vector spaces and apply them to a surprisingly wide array of systems with linear properties. One of the interesting things about this was that you could define a series of unique real number coordinates for a given series of independent basis vectors in the system.

It struck me the other day that there is an interesting, albeit slightly different pattern in the natural numbers. Any natural number can be written as the product of natural powers of primes. In a sense, it seems like the primes form a kind of 'basis' for the natural numbers, with the series of powers being a kind of 'coordinate'.

1. Is there is a name for this pattern?

2. If so, are there are other kinds of sets that can be decomposed as products of powers in this way, with similar generic results we can deduce for how these 'products of independent factors' behave?

I apologize for the lack of clarity here, but my unfamiliarity with the terminology makes it difficult to describe.

• Have a look at this answer : math.stackexchange.com/questions/6244/…
– Amr
Commented Apr 16, 2014 at 0:32
• @Amr, there is an interesting example in that link of using the set of the logarithms of primes as a vector space, but I'm unclear on how this connects with representing a number as a product of primes. I'm mainly curious on this apparent pattern of a 'weighted product' (rather than a 'weighted sum') and whether it relates to a more general concept like vector spaces, but for products. Commented Apr 16, 2014 at 0:56
• @Dan It is isomorphic to your example, only written as an additive (vs. multiplicative) group) by applying $\,\ \ell = {\rm log}\!:\,$ $\ p_1^{r_1}\cdots\,p_n^{r_n}\,\overset{\large \ell}\mapsto\, r_1\, \ell(p_1) +\,\cdots+ r_n\, \ell(p_n),\,\ r_i\in\Bbb Q.\ \$ Commented Apr 16, 2014 at 1:25
• @Bill, ah, interesting. So a 'product space' like this can be treated as a vector space as long as you can take the log of the factors. Commented Apr 16, 2014 at 2:00
• @Dan Bryant: this technique is used in the factoring algorithm en.wikipedia.org/wiki/Quadratic_sieve by Carl Pommeance.
– Lehs
Commented Sep 22, 2014 at 14:23