2
$\begingroup$

This question is from my math olympiad textbook. The exercise says that :

I want to prove :

If $x^y +1 $ with integer $x>1$ is prime , then $x$ must be even and $y$ must be a power of two ($1$ is also possible).

I thought that if $x^y +1 $ is prime ,then it must be odd number ,so $x^y$ is even and $x$ is even. However , i could not manage to show that $y=2^m$.

Can you help me to show it ?

$\endgroup$
9
  • 1
    $\begingroup$ The community appreciates your efforts to provide context and format in mathjax as a beginner! $\endgroup$ Oct 13, 2022 at 14:54
  • $\begingroup$ For a help, see also this post. $\endgroup$ Oct 13, 2022 at 14:55
  • $\begingroup$ If $y$ has an odd prime factor , say $p$ , then $x^{y/p}+1$ is a nontrivial factor of $x^y+1$ $\endgroup$
    – Peter
    Oct 13, 2022 at 15:03
  • $\begingroup$ If $x=6$ and $y=1$, then $x^y + 1 = 7$ .. so .. I miss something, no ? $\endgroup$ Oct 13, 2022 at 15:03
  • $\begingroup$ @MrSmithGoesToWashington You are right that $y=1$ is also possible. $\endgroup$
    – Peter
    Oct 13, 2022 at 15:04

1 Answer 1

5
$\begingroup$

Proof by contrapositive: Let the factorisation of $y$ be $y=2^M \cdot s$, where $s$ is an odd number, $s>1$ and $M\geq 0$, $M$ is an integer. Then, $$x^y+1=\bigg(x^{(2^M)}\bigg)^s+1$$$$=(x^{(2^M)}+1)\left(\bigg(x^{(2^M)}\bigg)^{s-1}-\bigg(x^{(2^M)}\bigg) ^{s-2}+…+1\right)$$ which is a product of two factors each greater than $1$. Hence it is composite.

Thus for the desired expression to be prime, $y$ must be of the form $2^m$ for some $m$.

$\endgroup$
2
  • $\begingroup$ So you assume that y is even .. ? $\endgroup$ Oct 13, 2022 at 15:27
  • $\begingroup$ No I don’t. M could be 0 as well. I will add that bit. If M=0, then the expression is divisible by x+1. $\endgroup$ Oct 13, 2022 at 15:56

You must log in to answer this question.