2
$\begingroup$

We have $n \ne 3k$ with $k\in \mathbb{N}$ and the integer $4n^2+3$. I think the first thing is to prove that this integer has a prime factor $p\equiv 7 [12]$.

I don't have idea to begin.

Thanks in advance !

$\endgroup$
4
  • $\begingroup$ hint: any prime factor $p$ of $4n^2+3$ must be $1\pmod{3}$, since $-3$ is a square mod $p$ (quadratic reciprocity). $\endgroup$
    – ArtW
    Jun 9, 2016 at 15:54
  • $\begingroup$ @ArtW I have to use the chinese lemma ? $\endgroup$
    – Maman
    Jun 9, 2016 at 15:59
  • $\begingroup$ Is $p\equiv 7 [12]$ a new notation for $p\equiv 7 \bmod 12$? I've never seen it before. $\endgroup$
    – TonyK
    Jun 9, 2016 at 16:24
  • $\begingroup$ @TonyK french notation ! $\endgroup$
    – Maman
    Jun 9, 2016 at 16:59

2 Answers 2

6
$\begingroup$

The proof below is a variant of Euclid's proof that there are infinitely many primes, or more precisely that given a finite collection of primes, there is a prime not in the collection.

Let $p_1,p_2,\dots, p_t$ be primes of the form $12k+7$. Let $$N=(2p_1p_2\cdots p_t)^2+3.$$ We will show that $N$ has a prime divisor $p$ of the form $12k+7$.

Note that if $p$ divides $N$ then $-3$ is a quadratic residue of $p$. By quadratic reciprocity it follows that $p\equiv 1\pmod{3}$. (Here, depending on what has been proved in your course so far, there may be some detail to fill in.)

So $p\equiv 1\pmod{12}$ or $p\equiv 7\pmod{12}$. But the prime divisors of $N$ cannot be all of the shape $12k+1$, else $N$ itself would be of the shape $12k+1$, and it isn't.

We conclude that $N$ has a prime divisor $p$ of the shape $12k+7$. It is clear that this $p$ cannot be equal to any of the $p_i$, and the result follows.

Appendix: Non-QR proof that $N$ will have no prime factors with shape $6k-1$

Suppose that there exist whole numbers $P, k$ such that $q=6k-1$ is prime and

$P^2\equiv -3\bmod q$ Eq. 1

Then we also have

$P^2\equiv (P+q)^2\bmod q$

and either $P$ or $P+q$ will be odd. Therefore for some whole number $m$

$(2m+1)^2\equiv -3\bmod q$

Expanding and collecting:

$4m^2+4m+4=4(m^2+m+1)\equiv 0\bmod q$

As $4$ is prime to $q$ we divide by that factor and continue:

$m^2+m+1\equiv 0\bmod q$

$(m^2+m+1)(m-1)=m^3-1\equiv 0\bmod q$

$m^3\equiv 1\bmod q$

$m^{6k}=(m^3)^{2k}\equiv 1\bmod q$ Eq. 2

Now Fermat's Little Theorem forces $m^{6k-2}\in\{0,1\}\bmod q$. Clearly $m^{6k-2}\equiv 0\bmod q$ contradicts Eq. 2. If instead $m^{6k-2}\equiv 1\bmod q$ then Eq. 2 forces $m\in\{-1,1\}\bmod q$. The latter then implies

$P^2\equiv (2m+1)^2\in\{1,9\}\bmod q$

which contradicts Eq. 1. Since all possibilities for $m$ lead to a contradiction the assumption of Eq. 1 cannot be true for any $P, k$.

$\endgroup$
9
  • $\begingroup$ If $p$ divides $N$, $p$ divides $4$ and $3$ ? $\endgroup$
    – Maman
    Jun 9, 2016 at 16:13
  • $\begingroup$ If $p$ divides $N$, then $p$ must be odd, since $N$ is odd. And $p$ cannot be $3$. For if $3$ divides $N$ then $3$ divides $4(p_1\cdots p_t)^2$, which is impossible, since all the $p_i$ are of the shape $12k+7$. $\endgroup$ Jun 9, 2016 at 16:18
  • $\begingroup$ I don't understand "$p\equiv 1\pmod{3}$ so $p\equiv 1\pmod{12}$ or $p\equiv 7\pmod{12}$" ? $\endgroup$
    – Maman
    Jun 9, 2016 at 16:58
  • $\begingroup$ Any number congruent to $1$ modulo $3$ is congruent to one of $1$, $4$, $7$, or $10$ modulo $12$. Since $p$ is odd, it cannot be congruent to $4$ or $10$ modulo $12$, which leaves the possibilities $p\equiv 1\pmod{12}$ and $p\equiv 7\pmod{12}$. $\endgroup$ Jun 9, 2016 at 17:05
  • $\begingroup$ One last thing, how do you deduce that $-3$ is a quadratic residue of $p$ ? $\endgroup$
    – Maman
    Jun 9, 2016 at 17:32
1
$\begingroup$

Dirichlet's theorem on arithmetic progressions tells you that there is infinitely many primes $p$ such that

$$p=a\pmod k$$

if $a\wedge k=1$.

And in your case you have $7\wedge 12=1$ so you're good.

$\endgroup$
3
  • 1
    $\begingroup$ Is $a\wedge k$ that a new notation for $\gcd(a,k)$? I've never seen it before. $\endgroup$
    – TonyK
    Jun 9, 2016 at 16:25
  • $\begingroup$ In France we often use that instead of $\text{gcd}(a,k)$, and sometimes we even use $(a,k)$. I didn't know it wasn't commonly use ! $\endgroup$
    – E. Joseph
    Jun 9, 2016 at 22:41
  • $\begingroup$ @TonyK I also think it is rare in this context, but it is logical! The natural numbers form a lattice under divisibility, and $a\wedge b$ is a common notation for meet - just what the doctor ordered here :-) $\endgroup$ Jun 10, 2016 at 5:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .