- #1
John Creighto
- 495
- 2
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.
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.
x+p1*n1
x+p2*n2
x+p3*n3
which are unique when x<p1p2p3
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.