0
$\begingroup$

For any integer $N$, can you find an odd prime $p$ such that $\frac{p^2-1}{4}$ is coprime to $N$?

This is equivalent to asking: Does there exist a prime $q$ which divides $\frac{p^2-1}{4}$ for every odd prime $p$?

$\endgroup$
  • $\begingroup$ Yes, q = 2. Bu I assume you mean q is odd and p > 3. $\endgroup$ – fleablood Oct 1 '15 at 7:29
  • $\begingroup$ Which is to say p^2 - 1/4 is never a power of 2. Which... it never is unless p =3. $\endgroup$ – fleablood Oct 1 '15 at 7:34
  • $\begingroup$ As 24 divides p^2 - 1 for all p >= 5, maybe you meant (p^2 - 1)/24? Then for example 7 => 2, 11 =>5, 13 => 7 and 17 => 12=3*4, the first composite number and ... um, now I lost track what the question was supposed to be. N to not have a coprime generated N must be a product of all the primes and prime factors generated requiring only a finite number of primes and prime factors generated. Is this the case? I doubt it but I doubt I can prove it. $\endgroup$ – fleablood Oct 1 '15 at 8:06
2
$\begingroup$

Not if $N$ happens to be even.

$\endgroup$
  • $\begingroup$ Oh god damnit you're right. What's the larger framework for this? This isn't really a question about quadratic residues, it's not really CRT... $\endgroup$ – oxeimon Oct 1 '15 at 6:58
  • $\begingroup$ And if N is odd p = 3 will always work. $\endgroup$ – fleablood Oct 1 '15 at 7:13
  • $\begingroup$ And if $N$ is odd and divisible by $3$, $p=3$ is the only solution. $\endgroup$ – Robert Israel Oct 1 '15 at 7:15
1
$\begingroup$

$\frac{p^2 - 1}{4} = \frac{p-1}{2}\frac{p + 1}{2} $ is always even. So if N is even, no.

$\frac{3^2 - 1}{4} = 2$. So f N is odd, yes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.