# Thread: prime numbers

1. ## prime numbers

Hi,

just stuck up with questions on prime numbers.

1) is 5^50 + 5^25 + 1 prime?

2) for how many prime p, p+8 and p+14 also prime?

Thanks

2. ## Re: prime numbers

1) $\displaystyle x^{50}+x^{25}+1$ is divisible by $\displaystyle x^2+x+1$ in $\displaystyle \Bbb{Z}[x]$, so no, it is not prime. $\displaystyle 5^2+5+1=31$ making that number divisible by 31.

2) haven't thought about it

3. ## Re: prime numbers

could you explain how you figured x^2+x+1
will divide the expression x^50+x^25+1

4. ## Re: prime numbers

It is an expression of the form $\displaystyle x^{2k}+x^{k}+1$, which is divisible by $\displaystyle x^2+x+1$ for all $\displaystyle k$.

5. ## Re: prime numbers

Originally Posted by SlipEternal
It is an expression of the form $\displaystyle x^{2k}+x^{k}+1$, which is divisible by $\displaystyle x^2+x+1$ for all $\displaystyle k$.
Not true

$\displaystyle x^6+x^3+1$ is not divisible by $\displaystyle x^2+x+1$

6. ## Re: prime numbers

Originally Posted by SlipEternal
It is an expression of the form $\displaystyle x^{2k}+x^{k}+1$, which is divisible by $\displaystyle x^2+x+1$ for all $\displaystyle k$.
It seems to me this is only true when k = 1 (mod 3). Fortunately, this is the case for k = 25.

(Essentially, this happens because $x^2 + x + 1$ has "3 terms", so we want $2k + 1$ to be divisible by 3 (a general polynomial of degree n has n+1 terms)).

7. ## Re: prime numbers

Oh, I remembered proving something about it in my algebra class years ago. That must have been it. My memory is not what it used to be.

8. ## Re: prime numbers

Originally Posted by SlipEternal
Oh, I remembered proving something about it in my algebra class years ago. That must have been it. My memory is not what it used to be.
Nor mine, amigo, nor mine.

9. ## Re: prime numbers

Originally Posted by Deveno
It seems to me this is only true when k = 1 (mod 3). Fortunately, this is the case for k = 25.

(Essentially, this happens because $x^2 + x + 1$ has "3 terms", so we want $2k + 1$ to be divisible by 3 (a general polynomial of degree n has n+1 terms)).
It is true if k = 1 or 2 mod 3

If k = 0 mod 3 then the division leaves a remainder = 3

10. ## Re: prime numbers

Originally Posted by Idea
It is true if k = 1 or 2 mod 3

If k = 0 mod 3 then the division leaves a remainder = 3
Yup. I forgot we could "go two, skip one" and still have everything cancel in the $k = 3n + 2$ case. See above.

11. ## Re: prime numbers

For (2), I would think it hard to prove there are only finitely many such primes. Usually,there is a proof that there are infinitely many such primes. So, I would attempt a proof by contradiction starting with the proposition that there are only finitely many primes $\displaystyle p$ such that $\displaystyle p+8$ and $\displaystyle p+14$ are both prime. Have you attempted this at all?

12. ## Re: prime numbers

I was puzzled by the divisibility fact mentioned above. Since others might also have been puzzled, here's a proof:

13. ## Re: prime numbers

Originally Posted by SlipEternal
For (2), I would think it hard to prove there are only finitely many such primes. Usually,there is a proof that there are infinitely many such primes. So, I would attempt a proof by contradiction starting with the proposition that there are only finitely many primes $\displaystyle p$ such that $\displaystyle p+8$ and $\displaystyle p+14$ are both prime. Have you attempted this at all?
Such a prime, if it exists, must be of the form $6k + 5$. To see this, note that:

$6k$ is divisible by 6
$6k + 2$ and $6k + 4$ are divisible by 2
$6k + 3$ is divisible by 3.

That leaves only $6k + 1$ and $6k + 5$. If we have $p = 6k+1$, then $p+8 = 6k + 9$ is divisible by 3.

(this is really just saying $p$ is of the form $3n + 2$).

14. ## Re: prime numbers

Or, for question 2, with the exception of p=5, try modulus 30 to weed out the 5's later on. XD
All candidates listed: 5, 11, 17, 23, 29.
Clearly 11+14=25, 17+8=25, and 5|25, so the first three can be weeded out.
Now, check p if p=23 or 29 (mod 30)

15. ## Re: prime numbers

p=3,p+8=11,p+14=17 has p=3 not congruent to 5 (mod 6). So, that should be amended p=3 or $\displaystyle p \equiv 5\pmod{6}$

Then, you can find congruences mod other primes.
p=5 or
$\displaystyle p\equiv 1,4\pmod{5}$

p=7 or
$\displaystyle p\equiv 1,2,3,4,5\pmod{7}$

p=11 or
$\displaystyle p\equiv 1,2,4,5,6,7,9,10\pmod{11}$

p=13 or
$\displaystyle p\equiv 1,2,3,4,6,7,8,9,10,11\pmod{13}$

For primes $\displaystyle q>13$, either $\displaystyle p=q$ or $\displaystyle p{\not \equiv}q,q-8,q-14\pmod{q}$

Not sure if that helps at all.