How to Solve 32n + 3 = 0 mod p When p is Prime?

[ramsey2879]

If p is prime > 2 then there is a easy way to solve 32n+3 = 0 mod p

if p = 1 mod 8 then m = (p-1)/4 and n = m(m+1)/2 mod p
if p = 3 mod 8 then m = (p-3)/4 and n = m(m+1)/2 mod p
if p = 5 mod 8 then m = (p-5)/8*2 + 1 and n = m(m+1)/2 mod p
if p = 7 mod 8 then m = (p-7)/8*2 + 1 and n = m(m+1)/2 mod p

Strange how triangular numbers relate to primes!

Can anyone give a proof for this relation?

 

[matt grime]

If you just substitute in the expression for n in terms of p it drops out.

e.g if you take the p=1 mod 8 example

32(p-1)(p+3)/2*4*4 +3 = -3+3=0 mod p.

The others are the same.

It doesn't appear too hard to generate other relations like this. Of course had you not chosen 32 and 3 you would not have this explicit relation with triangular numbers. You have dropped into the trap of looking at your probabilities a posterii. Note that 32/4=8 and you're looking at p mod 8.

 

[shmoe]

p doesn't have to be prime either, those solutions still work.

edit- you can also combine the p=1 and 5 mod 8 cases, both have m=(p-1)/4. Likewise for the other two, i.e. just look at p mod 4.

 

[ramsey2879]

p doesn't have to be prime either, those solutions still work.

edit- you can also combine the p=1 and 5 mod 8 cases, both have m=(p-1)/4. Likewise for the other two, i.e. just look at p mod 4.

Your right. The formula for n is much simpler if you look at it mod 4.

I stumbled on to this by chance. Looking at the problem to find n such that solves 32n + 3 = 0 mod p, the solution escapes any reasoned thought.
As you have shown, the proof of the solution to this problem is quite simple for odd p. Thanks
It is not the case for even p. For some even p there is no solution at all, and I haven't found a relation that determines which even p have solutions or a formula for those cases.

 

[matt grime]

There are no solutions for any even p.

You're trying to find n and t so that 32n+3=pt. If p is even then the RHS is even and the LHS is always odd so there are no solutions.

 

[Playdo]

solve 32n+3 = 0 mod p

Could'nt we also do it this way?

Rewrite the equation as $32n+3 = kp$. Rewrite that as

(1) $$kp - 32n = 3$$

Now this linear diophantine equation has solution (n,p) only when k is relatively prime to 32. The rrs mode 32 is {1,3,5,7,9,11,13,15,19,21,23,25,27,29,31}. Let one of these be denoted by r.

$$(32t+r)p - 32n = 3$$

So for any prime P and reduced residue of 32, R we have

$$Pt - n = \frac {3-RP}{32}$$

Which can be shown either to exist or not as a diophantine equation depending on whether 32|(3-RP).

So although this is not your typical closed form solution you can check easily to see if a given residue and a given prime allow a solution. When 32|(3-RP) we know that there is at least one solution t=3-RP and [itex]n = P(3-RP)-\frac {3-RP}{32}[/tex]

Then we can write all of them as

t = 3-RP + s
$$n = P(3-RP)-\frac {3-RP}{32} - s$$

s is an integer of our choosing.

This is intersting in that it shows us that while t and n are discrete linear in the residues, t discrete linear in the primes but n is discrete quadratic in the primes. That begs the follwing question, clearly

$$-RP^2+(3 -\frac {R}{32})P-(\frac {3}{32} +s+n)=0$$

So since s can be any integer, for every s there is a correspondence established between the set of primes and some subset of the integers, represented by n. If one were searching for a prime in a given interval this last equation could be used with n as a search parameter. The question is will all integer P be prime or will there be pseudo-primes? For a given interval and value for s any primes found should be denoted s-primes. So then are there intervals for which no primes are found unless s is very very large? We would not want to use this equation to search for primes on intervals where the number of possible values for s or n became very large. Those questions would have to be addressed.

Another question I find interesting here is this. Is it true that
$\{z|z=\frac {3-RP}{32}, r \in rrs mod 32, P - prime\}$ is actually the set of integers? Is it further true that $\{z|z=\frac {3-RP}{B}, r \in rrs mod B, P - prime, gcd(B,P)=1\}$ is actually the set of integers.

 

[matt grime]

Your last (two) questions are trivially false. They are equivalent to the statements that for every integer z, 3-32z is p, a prime, times some number in the reduced residue system mod 32 and that is obviously false.

You can insert forced spaces in latex with \ , a slash followed by a space. Things like rrs, mod and prime should be typeset in roman, not in italics. I think we can use \text{foo} to do that here, or if not the {\rm foo} might work.

$$\left\{ z\ | z \in \mathbb{Z},\ z=\frac{3-rp}{32},\ r \in \text{rrs mod} 32, \ p\ \text{prime}\right\}$$

 

[shmoe]

This equation isn't hard to solve. There is a solution exactly when p is odd (prime is irrelevant), and in this case it is a unique residue class mod p.

It's not hard to find either, if p=4n+1 say, then ((p-1)/4)*4=-1 mod p, ((p+3)/4)*4=3 mod p, and one of (p-1)/4 or (p+3)/4 is even, so we know ((p-1)/4)*((p+3)/4)/2 is an integer, and when multiplied by 32 is -3 mod p, so this is our solution. (similar if p=4n+3). All others lie in the same residue class mod p.

Which can be shown either to exist or not as a diophantine equation depending on whether 32|(3-RP).

And when it's not, you've got nothing. This is in fact usually the case, for any odd number p, there is only one choice of r out of the 16 that will work.

Of course you can actually find the only working r if you want, just find the inverse of p mod 32 and multiply by 3. You can find n this way, with the 16 cases for p mod 32. They'll reduce to the above mod 4 considerations, but not before much work.

So although this is not your typical closed form solution you can check easily to see if a given residue and a given prime allow a solution. When 32|(3-RP) we know that there is at least one solution t=3-RP and [itex]n = P(3-RP)-\frac {3-RP}{32}[/tex]

Then we can write all of them as

t = 3-RP + s
$$n = P(3-RP)-\frac {3-RP}{32} - s$$

s is an integer of our choosing.

You want that to be -p*s in your n, not -s. This is just getting all n in this residue class mod p.

This is intersting in that it shows us that while t and n are discrete linear in the residues, t discrete linear in the primes but n is discrete quadratic in the primes. That begs the follwing question, clearly

$$-RP^2+(3 -\frac {R}{32})P-(\frac {3}{32} +s+n)=0$$

So since s can be any integer, for every s there is a correspondence established between the set of primes and some subset of the integers, represented by n. If one were searching for a prime in a given interval this last equation could be used with n as a search parameter. The question is will all integer P be prime or will there be pseudo-primes? For a given interval and value for s any primes found should be denoted s-primes. So then are there intervals for which no primes are found unless s is very very large? We would not want to use this equation to search for primes on intervals where the number of possible values for s or n became very large. Those questions would have to be addressed.

So you're hoping to fix s and r, then try putting in values of n and hope the reulting p is a prime? Have you actually tried doing this to see what happens? Can you make these p's land in whatever interval you were looking for primes in? Are they often integers, let alone prime?

 

[Playdo]

You want that to be -p*s in your n, not -s. This is just getting all n in this residue class mod p.

No because we are just solving the satandard linear diophantine equation in t and n and the parameter s is multiplied by the gcd of the coefficients which in this case is 1.

Those last two statements were intended to evoke just the response you gave. What sets are they?

And if for any odd p one and only one of the residues works for a solution how are the residues ordered by consecutive odd p? Are we talking about all possible permutations that must pass or are we talking about one particular ordering of the residues that is repeated over and over for consecutive odd p.

I have to praise you though on noticing that it suffices to use p odd and not prime. It is an important point that sometimes by restricting or enlarging perspective we find proofs that may not exist on other sets.

Just for you and to help allay my blues over not finding a job yet, I am going to sit down and go over that Goldbach proof I was talking about. It will probably fizzle, but I am guessing I am going to end up with a question about the distribution of primes similar to Wilson's Theorem, between p and 2p there is at least one other prime. Only I think it will have ot be more restrictive. I will probably see if you have any insights on that. I'll try to post tomorrow night.

 

[shmoe]

No because we are just solving the satandard linear diophantine equation in t and n and the parameter s is multiplied by the gcd of the coefficients which in this case is 1.

You were looking for solutions n and t of:

$$Pt - n = \frac {3-RP}{32}$$

Then gave a solution in terms of P and R under the condition 32|(3-RP), these were fine. You then claim for any integer s, t+s and n-s will give a solution as well, but if you sub these in, the left hand side is:

$$P(t+s)-(n-s)=Pt+Ps-n+s=\frac{3-RP}{32}+Ps+s$$

That's not a solution to the equation you are after (unless s=0 of course).

You'll want to check that theorem on linear diophantine equations again. I think you are after something like:

if gcd(a,b)|c then ax+by=c has infinitely many solutions. fix any specific solution x_0, y_0 say, then all solutions are given by:

$$x=x_0+\frac{b}{\gcd (a,b)}t,\ y=y_0-\frac{a}{\gcd (a,b)}t$$

as t ranges over the integers. See the difference?

Those last two statements were intended to evoke just the response you gave. What sets are they?

What response are you talking about?

And if for any odd p one and only one of the residues works for a solution how are the residues ordered by consecutive odd p? Are we talking about all possible permutations that must pass or are we talking about one particular ordering of the residues that is repeated over and over for consecutive odd p.

Is this about the original equation or after you introduced the 'r'? I'm guessing you're asking about the necessary r's given p's and of course this is cyclic. r depends only on p mod 32 (remember how I said to find this r). You can work out the order easily enough, by hand or mathematica will do it in a second.

I have to praise you though on noticing that it suffices to use p odd and not prime. It is an important point that sometimes by restricting or enlarging perspective we find proofs that may not exist on other sets.

save your praise, it's just elementary facts about linear congurences.

... but I am guessing I am going to end up with a question about the distribution of primes similar to Wilson's Theorem, between p and 2p there is at least one other prime.

That's not Wilson's theorem, it's Bertrand's Postulate.

 

[ramsey2879]

--Re 32$$n$$ = -3 $$\mod p$$--This equation isn't hard to solve. There is a solution exactly when p is odd (prime is irrelevant), and in this case it is a unique residue class mod p.

It's not hard to find either, if p=4n+1 say, then ((p-1)/4)*4=-1 mod p, ((p+3)/4)*4=3 mod p, and one of (p-1)/4 or (p+3)/4 is even, so we know ((p-1)/4)*((p+3)/4)/2 is an integer, and when multiplied by 32 is -3 mod p, so this is our solution. (similar if p=4n+3). All others lie in the same residue class mod p.

Thanks for your concise treatment. Let me re-phrase it.

Let $$p = a \ \mod \ 4$$,

Then $$\frac{(p-a)*(p-a+4)}{32}$$ is a triangular number, $$n$$,

Furthermore for odd p, as all odd numbers are either congruent to 1 or 3$$\mod\ 4$$ and since $$1 = -3\ \mod\ 4$$, then $$32*n = -(3*1) \ \mod\ 4$$.

 

[ramsey2879]

There are no solutions for any even p.

You're trying to find n and t so that 32n+3=pt. If p is even then the RHS is even and the LHS is always odd so there are no solutions.

Your right, I confused 2 separate issues.

Formerly, I was looking for "a" mod p such that 4a*(8a+1) = a mod p There is an unique solution for all odd p which reduces to the present problem . For some even p, not all, there are solutions to this former question also.