Let $a, k \geq 2$.
If $a^k + 1$ is a prime, conclude that $k$ is a power of $2$. Show that the converse is not true.
The hint is: if $n$ is odd, then $x^n + 1$ has a factor of $x + 1$. Please help, I don't know how to solve this.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ You should assume $a>1$, because $1^3+1$ is prime but $3$ is no power of $2$. $\endgroup$– gammatesterCommented Sep 15, 2015 at 13:00
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
If $k$ is odd then you have the factorization $$a^k+1=(a+1)(a^{k-1}-a^{k-2}+a^{k-3}-....-a+1)$$ So $a^k+1$ can not be prime. For the converse take for example $k=2,\,a=5$ or just any odd number $a$ and $k=2^l$ for some $l\ge 1$
answered Sep 15, 2015 at 12:55
-
1$\begingroup$ This shows that $k$ is even. Does it show that $k$ is a power of $2$? $\endgroup$ Commented Sep 15, 2015 at 13:13
-
$\begingroup$ @ Thumbnail you are right, I should have added this, like it is in Bernard's answer. $\endgroup$ Commented Sep 15, 2015 at 13:26
$\begingroup$
$\endgroup$
If $k$ is not a power of $2$,, it can be written as $\;2^l(2m+1)$, hence $$a^{2^l(2m+1)}+1=\bigl(a^{2^{\scriptstyle l}}\bigl)^{2m+1}+1=\bigl(a^{2^{\scriptstyle l}}+1\bigr)\bigl(a^{2^{\scriptstyle l}2m}-a^{2^{\scriptstyle l}(2m-1)}+\dots-a^{2^{\scriptstyle l}}+1\bigr).$$
$\begingroup$
$\endgroup$
As for the converse, you only need some examples, like cases where a is odd, or you can also use the same argument that was used in the other direction, for suitable values of a: for a^k +1 to be a prime you have seen the argument that explains that k has to be a power of 2, otherwise if it contains an odd prime factor you can use a case of factorization of polynomials to factor your number. With the same argument, if the given a is a perfect power with odd exponent, for example a= 2^3 = 8, or a= 6^5, then you can use this exponent to factor a^k + 1 exactly with the same argument (the exponent in a multiplies with the k and you end up again with an exponent containing an odd prime divisor). Let's see an example: a = 2^3 = 8. Take k = 2^7. Well, a^k +1 is now a big number, but since the "basis" a is a cube, a^k + 1 = 8^k + 1 = 2^(3k) + 1 must be divisible by 2^k + 1, thus it is a composite number. So this is an example where k = 2^7 is a power of 2, but still a^k + 1 is not a prime (and a is even).
For a=2 or other even numbers that are not odd perfect powers, still it happens many times that a^k + 1 is composite with k a power of 2, but in these cases there is no direct way of deducing this from a polynomial factorization, it can be seen as a "frequent coincidence" (or you can look for deeper reasons that justify this). A famous example is the Fermat number 2^32 + 1, a number that was thought to be a prime by Fermat but was later proved (by Euler) to be divisible by 641.
