Linear Combination of Primes

John Creighto

Was thinking a bit about linear combination of primes and my conclusions are bellow. I presume their is some theorem to capture this but I don't know it's name.

If p1 p2 are primes and n1 or n2 are positive integers, then there should be unique a minimum n1 n2 pair such that:

[tex]x=p_1n_1+p_2n_2 \pmod{p_1p_2}[/tex]

and all solutions should be of the form p_1n_1+p_2n_2 + m* p_1*p_2

Now If we introduce a third prime we know x satisfies:

[tex]x= a_1 \pmod{p_1}[/tex]
[tex]x= a_2 \pmod{p_2}[/tex]
[tex]x= a_3 \pmod{ p_3}[/tex]

where:

[tex]a_1 = p_2n_2+p_3n_3 \pmod{p_1} [/tex]
[tex]a_2 = p_1n_1+p_3n_3 \pmod{p_2} [/tex]
[tex]a_3 = p_1n_1+p_2n_2 \pmod{p_3} [/tex]

all solutions should be of the form: edit: part in quotes bellow needs to be fixed.

Now what happens if we wrap the space into something smaller then p1*p2*p3 as would be done in a hash table. Say, we wrap it into a power of two as is done in the java class hashmap.

Then I think this means

[tex]a1=a2=a3 \pmod{2^n}[/tex]

because

we want x to have unique values in the range 0 to 2^n so

[tex]x= a_4 \pmod{2^n}[/tex]
[tex]x= a_5 \pmod{2^n}[/tex]
[tex]x= a_6 \pmod{ 2^n}[/tex]

But the mod part of our equations is no longer pair wise prime and hence the solutions have to be equal with respect to modulo the greatest common divisor of the modulo part otherwise their is not a unique x. However, this looks quite difficult to satisfy so I think I might be missing something in terms of understanding.

adriank

Chinese remainder theorem

John Creighto

Odd. I thought I mentioned that theorem in my original post. Anyway, what I was trying to do is use that theorem to map the unique solution space of a linear combination of primes in terms of their coefficients, and then see what consequences this has in terms of hash tables. The result is pretty trivial when you consider only two primes as you can apply modulo operations and then use the Chinese remainder theorem to show the range for which the linear combination representation is unique.

However if you have three primes the Chinese remainder theorem tells us that each unique value of a_1 a_2 and a_3 in

[tex]x= a_1 \pmod{p_1}[/tex]
[tex]x= a_2 \pmod{p_2}[/tex]
[tex]x= a_3 \pmod{ p_3}[/tex]

gives a unique value but we may not be able to produce all ordered pairs (a1 a2, a3) from a given (n1, n2,n3) because a1, a2 and a3 are defined as follows:

[tex]a_1 = p_2n_2+p_3n_3 \pmod{p_1} [/tex]
[tex]a_2 = p_1n_1+p_3n_3 \pmod{p_2} [/tex]
[tex]a_3 = p_1n_1+p_2n_2 \pmod{p_3} [/tex]


Let's look at a simple example p1=2 p2=3 p3=5 and

2+3=5 so

Here is a redundant mapping from (n1, n2, n3) to (a1, a2,a3)
(1,1,0)->(1,2,0)
(0,0,1)->(1,2,0)

I'm not sure if their are any other redundant mappings if we restrict, n1<p1, n2<p2 and n3<p3. Perhaps if we insure p3 is greater then the product of p1p2 we avoid redundant mappings.

John Creighto

Here is another linear combination prime question. Can every prime be constructed as a linear combination of smaller primes. It seems to work up to 17. Haven't tried it any further where the coefficient must be a positive coefficient less then the prime for which it is multiplied by.

John Creighto

I was looking at the solution to the Chinese remainder theorem on wikipedia. It seems there is a linear independent basis for the number which are the solution to the chinease remainder theorm:

Although the basis vector [tex]e_i [/tex] isn't a prime number and it isn't necessarily positive. It's still an interesting arthritic way to uniquely construct a set of numbers.

CRGreathouse

Yes. You can prove this with strong induction and Bertrand's postulate.

daveyp225

take any linear combination of primes p,q, (not equal) ap+qb equal to 1, we are guaranteed there exist such a,b. then just multiply through by any prime you want.

so, all primes (in fact integers) are a linear combination of any two primes.

John Creighto

Interesting technique. Of course this doesn't work if we restrict our coefficients to positive numbers.