6
$\begingroup$

As the title says we seek to

Find a prime that divides $14^7+14^2+1$

There is a caveat though. This was part of a contest for high-school students so undergraduate Number Theory tools such as modular arithmetic should be avoided if we wish to remain true to the spirit of the competition.

That said, I did verify-employing exactly such tools-that if $p$ is the said prime then $p\neq2,3,5,7$.

Probably some form of simplifying the expression is required to solve it but it eludes me.

EDIT

The initial formulation of this question was "find the smallest such prime". This is highly unlikely to be achieved by pen and paper on the timeframe of a contest. For more details on why one can look at @lulu's answer below.

As noted on the comments by @JyrkiLahtonen, a similar question was posted before.

See here as well for answers.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ It does factor, but that doesn't tell me why one of the sides is the smallest prime: $(x^7+x^2+1)=(x^2+x+1)(x^5-x^4+x^2-x+1)$ $\endgroup$ – Peter Woolfitt Oct 27 '17 at 21:35
  • $\begingroup$ @lulu 3-digits Great..I thought about trial and error but that is discouraging. I will have the proposed solution available in a few hours but I am sure that it does not involve modular. $\endgroup$ – MathematicianByMistake Oct 27 '17 at 21:35
  • 1
    $\begingroup$ Related. That is closed for missing context, so I won't vote to close this as duplicate. It actually isn't because no attention to the smallest prime factor was given there. +1 to all $\endgroup$ – Jyrki Lahtonen Oct 27 '17 at 21:50
  • $\begingroup$ @JyrkiLahtonen I will edit again to link to your answer. Since it is a common cyclotomic polynomial (not common for me unfortunately) it might well be of interest again and in order to avoid future duplicates.. $\endgroup$ – MathematicianByMistake Oct 27 '17 at 22:00
  • $\begingroup$ Please link to Bill Dubuque's (=Number's) answer instead. It is more general. $\endgroup$ – Jyrki Lahtonen Oct 27 '17 at 22:02
12
$\begingroup$

We can factor the polynomial $$x^7+x^2+1=(x^2+x+1)\times (x^5-x^4+x^2-x+1)$$

Letting $x=14$ shows that $211$ is a prime factor. You still have to prove it is the least prime factor, but at least you can work with a smaller number.

Improve this answer
$\endgroup$
  • $\begingroup$ ...how do you know one of the sides is the smallest prime for $x=14$? $\endgroup$ – Peter Woolfitt Oct 27 '17 at 21:36
  • 1
    $\begingroup$ @PeterWoolfitt There were $4$ questions-if I am not mistaken this was the last one (most difficult?) and participants had $3$ hours to finish. $\endgroup$ – MathematicianByMistake Oct 27 '17 at 21:41
  • 2
    $\begingroup$ @MathematicianByMistake Oh, that's much easier. Thanks for clarifying! $\endgroup$ – lulu Oct 27 '17 at 21:45
  • 1
    $\begingroup$ Nice, though I wonder how does one arrive at this factorization with pencil and paper :) $\endgroup$ – Sil Oct 27 '17 at 21:46
  • 1
    $\begingroup$ @Ovi It's essentially cyclotomic. Obviously a primitive cube root of $1$ is a root so it is clear that $x^2+x+1$ is a factor. Actually, that remark is sufficient to solve the problem, but once you have one factor it is easy to find another. This sort of factoring comes up all the time in high school math challenge problems. $\endgroup$ – lulu Oct 27 '17 at 23:37
3
$\begingroup$

The reason we can get one factor immediately is that $7 \equiv 1 \pmod 3.$ As a result, both nontrivial roots of unity are roots of $x^7 + x^2 + 1,$ meaning that $(x - \omega)(x- \omega^2) = x^2 + x + 1$ must divide the polynomial $x^7 + x^2 + 1.$ Here $\omega^3 = 1$ but $\omega \neq 1$

If this seems uncomfortable, just consider that $x^2 + x + 1$ is the minimal polynomial for $\omega$ over $\mathbb Q,$ and must divide any polynomial for which $\omega$ is a root. Furthermore, the Gauss theorem on content tells us that the quotient polynomial has integer coefficients, not just rational.

Similar: the polynomial $x^{141} + x^{93} + x^{82} + x^{44} + 1$ is divisible by $x^4 + x^3 + x^2 + x + 1,$ consider a fifth root of unity.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Nice observation +1! $\endgroup$ – MathematicianByMistake Oct 27 '17 at 22:26
  • 1
    $\begingroup$ @MathematicianByMistake I added a quintic problem similar to the cubic. You could ask your friend to find a squared prime that divides $$ 3^{141} + 3^{93} + 3^{82} + 3^{44} + 1 $$ Oh, I see, contest rather than friend. $\endgroup$ – Will Jagy Oct 27 '17 at 22:55
  • $\begingroup$ @I will! (When he sees it I am not sure he will remain a friend for much longer though..) $\endgroup$ – MathematicianByMistake Oct 27 '17 at 23:00
1
$\begingroup$

$$x^7+x^2+1=x^7-x+x^2+x+1=x(x^3-1)(x^3+1)+x^2+x+1=$$ $$=(x^2-x)(x^2+x+1)(x^3+1)+x^2+x+1=$$ $$=(x^2+x+1)(x^5-x^4+x^2-x+1).$$

Improve this answer
$\endgroup$
  • $\begingroup$ Can down-voter explain us why did you do it? $\endgroup$ – Michael Rozenberg Feb 4 '20 at 16:11

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.