15
$\begingroup$

Let $p$ be prime number,and $n$ be postive integers, such $$p\mid n^3+n^2-2n-1, \quad n\ge 2$$ show that $$7\mid p^3-p$$

It maybe can use Fermat's little theorem?

$\endgroup$
  • 3
    $\begingroup$ A hint, may be a bit obscure :-): $x^3+x^2-2x-1$ is the minimal polynomial of $2\cos(2\pi/7)=\zeta_7+\overline{\zeta_7}$, $\zeta_7=e^{2\pi i/7}$. See my comments under this question for a way forward. Thinking about a more elementary way... (with high hopes that one exists) $\endgroup$ – Jyrki Lahtonen Aug 7 '17 at 5:33
  • $\begingroup$ @JyrkiLahtonen,I can't understand your hint,can you post more detail? $\endgroup$ – wightahtl Aug 7 '17 at 5:38
  • 3
    $\begingroup$ I don't know if this helps to find an elementary solution! But others may look at this and find a clue: $p \mid (3n+1)^3-21(3n+1)-7$. $\endgroup$ – Ghartal Aug 8 '17 at 16:03
12
$\begingroup$

Expanding my comments. I first give an answer using the machinery of . That argument relies on the theory of splitting of primes in cyclotomic fields and their subfields, most notably to identifying the action of the Frobenius automorphism which is particularly easy in a cyclotomic fields.

Following that answer I also give another answer using less technology - replacing the use of cyclotomic fields with a few basic facts about finite fields. Some readers may benefit from reading the second answer first, and then coming back to the first (provided they are at all familiar with algebraic number theory). The reason why I ordered the answers in this way is my way of handling Bill Dubuque's comment. Otherwise the key equation used in the second answer looks like it came out of a magic box.

I actually believe that there may be a way of replacing the use of finite fields in my second answer with Little Fermat (or something close to that). I don't have a good way of doing that myself (I have made a little bit of progress and am still thinking...). On with the first answer:


Let $\zeta=e^{2\pi i/7}$ be a primitive seventh root of unity, when $2\cos(2\pi/7)=\zeta+\zeta^{-1}$. We know that $m(x)=(x^7-1)/(x-1)=x^6+x^5+x^4+x^3+x^2+x+1$ is the minimal polynomial of $\zeta$. Denoting $f(x)=x^3+x^2-2x-1$ we then see that $$ \begin{aligned} f(\zeta+\zeta^{-1})&=(\zeta+\zeta^{-1})^3+(\zeta+\zeta^{-1})^2-2(\zeta+\zeta^{-1})-1\\ &=\sum_{j=-3}^3\zeta^j=\frac{m(\zeta)}{\zeta^3}=0. \end{aligned} $$ Therefore $f(x)$ is the minimal polynomial of $2\cos(2\pi/7)$.

Finally, let $L=\Bbb{Q}(\zeta)$, $K=\Bbb{Q}(\zeta+\zeta^{-1})$ be the given field extensions. For a rational prime $p\neq7$ we know that the corresponding Frobenius automorphism $\sigma_p$ in $Gal(L/\Bbb{Q})$ is uniquely determined by the requirement $\sigma_p(\zeta)=\zeta^p$. Assume that $n$ is an integer such that $p\mid f(n)$. This means that the norm $N_K(z)$ of the algebraic integer $z:=n-(\zeta+\zeta^{-1})\in K$ is divisible by $p$. Without loss of generality we can assume that $0<n<p$ implying that the norm has absolute value $<p^3$. Because $K/\Bbb{Q}$ is a cubic cyclic extension, this forces the prime $p$ to split into a product of three distinct prime ideals of $\mathcal{O}_K$, $p=\mathfrak{p}_1\mathfrak{p}_2\mathfrak{p}_3$, each with inertia degree $f(\mathfrak{p}_i\mid p)=1$. Without loss of generality we can assume that $\mathfrak{p}_1=(p,n-(\zeta+\zeta^{-1}))$, $\mathfrak{p}_2=(p,n-(\zeta^2+\zeta^{-2}))$, $\mathfrak{p}_3=(p,n-(\zeta^3+\zeta^{-3}))$. The information about the inertia degree is important here. When $f=1$ we know that the Frobenius automorphism must map $\mathfrak{p}_1$ to itself. Also, it must induce the identity mapping on the residue class field $\mathcal{O}_K/\mathfrak{p}_1$. In particular $z$ must be a fixed point of $\sigma_p$. But $$ z=\sigma_p(z)=n-(\zeta^p+\zeta^{-p}) $$ if and only if $p\equiv\pm1\pmod7$. This implies that $7\mid p^2-1$. Taking into account the possibility $p=7=f(2)$ we see that we always have $7\mid p(p^2-1)$.


Then the same in the language of finite fields, and without a semester's worth of algebraic number theory.

Assume that the prime $p\neq7$ and that $n$ is an integer such that $p\mid f(n)$. Because $\gcd(n,f(n))=1$ it follows that $n$ is not divisible by $p$. We can also conclude that $n$ is not congruent to $2$ modulo $p$, because then $n^3+n^2-2n-1$ would be congruent to $2^3+2^2-2\cdot2-1=7$ modulo $p$ contradicting the assumption $p\neq7$.

Consider the equation $$ x+\frac1x=n\qquad(*) $$ over the field $K=\Bbb{F}_p$. Let $\alpha$ be a solution of $(*)$ in some extension field of $K$. Because $n\not\equiv2\pmod p$ we can conclude that $\alpha\neq1_K$. But $$ \begin{aligned} &\alpha^3+\alpha^2+\alpha+1+\alpha^{-1}+\alpha^{-2}+\alpha^{-3}\\ =&(\alpha+\alpha^{-1})^3+(\alpha+\alpha^{-1})^2-2(\alpha+\alpha^{-1})-1\\ =&(n^3+n^2-2n-1)\cdot 1_K\\ =&0_K. \end{aligned} $$ Multiplying this by $\alpha^3$ gives $$ 0=1+\alpha+\alpha^2+\cdots+\alpha^6=\frac{\alpha^7-1}{\alpha-1}, $$ as $\alpha-1\neq0$. Therefore $\alpha^7=1$ and $\alpha$ has multiplicative order $7$.

But $(*)$ is a quadratic equation so $\alpha$ belongs to the quadratic extension $\Bbb{F}_{p^2}$. Its multiplicative group is known to be cyclic of order $p^2-1$, so we can conclude that $7\mid p^2-1$.

Including the case $p=7$ we have, again, shown that in all the cases $7\mid p^3-p$.


Hopefully it is clear that in the second solution $n$ plays the role played by $2\cos(2\pi/7)$ in the first solution while $\alpha$ handles the duties of $\zeta$.

$\endgroup$
  • $\begingroup$ So sorry to reduce "everything" to the known structure of the multiplicative groups of finite fields. When you have mastered the use of a hammer you tend to solve problems with nails... $\endgroup$ – Jyrki Lahtonen Aug 7 '17 at 6:20
  • $\begingroup$ Surely the answer would be much more instructive if you explained why we consider the equation $\,x+1/x = n,\,$ rather than simply pulling it out of a hat like magic. $\endgroup$ – Bill Dubuque Aug 7 '17 at 16:55
  • $\begingroup$ A fair point @BillDubuque. The motivation (from my comments under this as well as the linked quesion) comes from the given cubic being the minimal polynomial of the sum of a seventh root of unity and its reciprocal. Thinking about how to best explain the analogy of $n=2\cos(2\pi/7)$, $\alpha=\zeta_7$. I will still spend some time trying to turn this into an answer at "high school olympiad" level. Read: get rid of finite fields and their extensions. $\endgroup$ – Jyrki Lahtonen Aug 7 '17 at 18:36
  • $\begingroup$ It wouldn't surprise me if it has already been done in a prior answer. Approach0 lists 10 pages on this cubic polynomial (I didn't have time to browse them). Readers learning these topics might find some of those answers illuminating. $\endgroup$ – Bill Dubuque Aug 7 '17 at 18:46
  • 1
    $\begingroup$ I think I see what you mean, @CMonsour. Is this what you had in mind? $\endgroup$ – Jyrki Lahtonen May 2 '18 at 10:13
2
+25
$\begingroup$

A blind approach, although it will give the same solution.

The polynomial $f(x)=x^3+ x^2 - 2 x -1$ has discriminant $\Delta=49$, a square. Therefore, given a root $x_1$ of $f(x)$, the other roots can be expressed in terms of $x_1$ from the equality $$(x_2-x_3) = \frac{(x_1-x_2)(x_1-x_3)(x_2-x_3)}{(x_1-x_3)(x_2-x_3)}= \frac{\pm\sqrt{\Delta}}{f'(x_1)}$$ and combined with the equality $x_2+x_3= s-x_1= -1-x_1$ give the expression for the other roots.

Note that we have a GCD formula for $f$ and $f'$ involving the discriminant. In our case we have $$(-6 x -1)(x^3+x^2- 2 x -1)+ (2x^2 + x- 3)(3 x^2 + 2 x - 2)=7$$ and so if $\alpha $ is a root of $f$ then $$\frac{\sqrt{\Delta}}{f'(\alpha)}= \frac{7}{f'(\alpha)} = 2\alpha^2 + \alpha- 3$$

Therefore, if $\alpha$ is a root of $f$ in a field $F$ then $$\frac{1}{2}(-1-\alpha \pm (2\alpha^2 + \alpha- 3))= \alpha^2 - 2, - \alpha^2 - \alpha + 1$$ are also roots of $f$. Also,the product of their differences is $7$, so they are distinct if $7 \ne \operatorname{char} (F)$. In that case, starting from $\alpha$ a root we get all the roots in this way.

This works for any cubic with discriminant a square. This one is special, because we notice: $$\alpha \text{ root of }\ f \implies \alpha^2-2 \text{ root of }\ f$$ and we might recall the polynomial $x^2-2$ from $t^2 +\frac{1}{t^2}=(t+\frac{1}{t})^2-2$. Now we check that $$- \alpha^2 - \alpha -1 = (\alpha^2-2)^2 -2$$ if $\alpha$ is a root. So we may rephrase the above statement as (assume $7 \ne \operatorname{char}(F)$ $$t+\frac{1}{t} \text{root of }\ f \implies t^2 +\frac{1}{t^2} , t^4 +\frac{1}{t^4}\text{the other roots of }\ f$$

Now consider $p\ne 7$ such that $f$ has a root $\alpha$ in $F_{p}$. Consider then $t$ in $F_{p^2}$ such that $t+\frac{1}{t}=\alpha$. Then

$$t+\frac{1}{t}, t^2+\frac{1}{t^2}, t^4+\frac{1}{t^4}$$ are the distinct roots of $f$ , all in $F_{p}$. But then $t^8 + \frac{1}{t^8}$ must get us back to $t + \frac{1}{t}$. So... $t^8=t$ or $t^8=\frac{1}{t}$. First case gives us an element of order $7$ in $F^{\times}_{p^2}$ , so $7\mid p^2-1$. Second case we hope to exclude. Short of other ideas, we substitute:

$$f(t+\frac{1}{t})=\frac{t^6 + t^5 + t^4 + t^3 + t^2 + 1}{t^3}$$ Therefore $$t^6 + t^5 + t^4 + t^3 + t^2 + 1 = 0$$ and we get $t^7=1$, $t\ne 1$, so $t$ element of order $7$ in $\mathbb{F}_{p^2}^{\times}$.

Added: another approach: we have $$1+ (t+ \frac{1}{t}) + (t^2+ \frac{1}{t^2}) + (t^4 + \frac{1}{t^4}) = 0$$ so $$\frac{(t+ \frac{1}{t}-1)(t^6 + t^5 + t^4 + t^3 + t^2 + 1)}{t^3}=0$$

$\endgroup$
  • $\begingroup$ Nice. The case $t^8=1/t$ corresponds to the minimal polynomial $x^3-3x+1$ of $2\cos(2\pi/9)=\zeta_9+\overline{\zeta_9}$ as opposed to the minimal polynomial $x^3+x^2-2x-1$ of $2\cos(2\pi/7)$ which is what we have here. Anyway, the rule "$\alpha$ is a root $\implies$ $\alpha^2-2$ is a root" is shared by the minimal polynomials of all $2\cos(2\pi/m)$, $m$ odd. A consequence of $(2\cos x)^2-2=2\cos 2x$. $\endgroup$ – Jyrki Lahtonen Apr 26 '18 at 12:02
  • $\begingroup$ So a similar argument shows that if a prime $p\mid n^3-3n+1$ for some natural number $n$, then either $p=3$ or $p\equiv\pm1\pmod{18}$. $\endgroup$ – Jyrki Lahtonen Apr 26 '18 at 12:08
  • $\begingroup$ @Jyrki Lahtonen: Thanks! did not notice the cyclotomy before I read your answer, but had the substitution. Now, in retrospect, if we have an abelian Galois group we should search for the "magical substitution". Cheers! $\endgroup$ – Orest Bucicovschi Apr 26 '18 at 12:11
  • $\begingroup$ @Jyrki Lahtonen: I wonder what other tricks can work to produce "elementary" results. $\endgroup$ – Orest Bucicovschi Apr 26 '18 at 12:26
  • $\begingroup$ @Jyrki Lahtonen: It works also if $p\mid n^2 -2$ for some $n$. :-) But similarly,, how this has an "elementary" proof, maybe the others should have too, bypassing finite fields, using "real" methods. $\endgroup$ – Orest Bucicovschi Apr 26 '18 at 12:47
1
$\begingroup$

An alternative way is to consider the prime divisors of $a^3+a^2b-2ab^2-b^3$, and reduce the numbers by applying Thue's lemma.

Call a prime $p$ "bad" if $p\not\equiv0,\pm1\pmod7$, and there exist some co-prime integers $a,b$ such that $p$ divides $a^3+a^2b-2ab^2-b^3$. Suppose that there at least one bad prime, and take the least bad prime and the corresponding $a$ and $b$.

By Thue's lemma, there are some integers $0<k<p,c,d$ such that $ak\equiv c\pmod{p}$, $bk\equiv d\pmod{p}$, $|c|<\sqrt{p}$, and $|d|<\sqrt{p}$. Then $p$ divides $c^3+c^2d-2cd^2-d^3$. If $c$ and $d$ are not co-prime, we can divide them by their gcd. (Notice that at least one of $c$ and $d$ is not divisible by $p$, so this simplification does not destroy the divisibility by $p$.)

It can be verified that $c^3+c^2d-2cd^2-d^3\equiv\pm1\pmod7$ or $c^3+c^2d-2cd^2-d^3\equiv\pm7\pmod{49}$. Any case happens, there must be another "bad" prime divisor $q$ of $c^3+c^2d-2cd^2-d^3$. But $p$ is the least bad prime, so $q\ge p$; therefore $p^2\le pq\le|c^3+c^2d-2cd^2-d^3|<3\sqrt{p}^3$, so $p<9$.

The primes $2,3,5$ can be excluded manually.

$\endgroup$
1
$\begingroup$

This answer is a little more prosaic, but I hope it is also more approachable.

If $7\mid (p^3-p)=p(p^2-1)$ then either $p=7$ or $(p^2-1)=7m$. The latter case is true if $p$ has the form $14k\pm 1$. (NB The form $7k\pm 1$ satisfies the math, but to be prime the number must be odd; hence $14k\pm 1$).

If we look at $n^3+n^2-2n-1 \mod{14}$, all of the residues are from among $-1,\space 1,\space 7$. For $n=14j+i$ for $0\le i\le13$ the residues are respectively: $(-1,-1,7,1,1,-1,1,-1,-1,7,1,1,-1,1)$.

Thus $n^3+n^2-2n-1$ is always divisible by $7$ or a number of the form $14k\pm 1$. Thus if $p\mid (n^3+n^2-2n-1)$ it is either $7$ or has the form $14k\pm 1$. In either case $7\mid(p^3-p)$.

$\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.