# prime numbers

• Jul 31st 2014, 11:15 AM
nikhil
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
• Jul 31st 2014, 05:49 PM
SlipEternal
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
• Aug 1st 2014, 11:55 PM
nikhil
Re: prime numbers
could you explain how you figured x^2+x+1
will divide the expression x^50+x^25+1
• Aug 2nd 2014, 06:06 AM
SlipEternal
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$.
• Aug 2nd 2014, 06:39 AM
Idea
Re: prime numbers
Quote:

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$
• Aug 2nd 2014, 08:27 AM
Deveno
Re: prime numbers
Quote:

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)).
• Aug 2nd 2014, 08:34 AM
SlipEternal
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.
• Aug 2nd 2014, 09:30 AM
Deveno
Re: prime numbers
Quote:

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.
• Aug 2nd 2014, 09:43 AM
Idea
Re: prime numbers
Quote:

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
• Aug 2nd 2014, 11:52 AM
Deveno
Re: prime numbers
Quote:

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.
• Aug 2nd 2014, 12:33 PM
SlipEternal
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?
• Aug 3rd 2014, 05:40 PM
johng
Re: prime numbers
I was puzzled by the divisibility fact mentioned above. Since others might also have been puzzled, here's a proof:

http://i57.tinypic.com/15h036h.png
• Aug 3rd 2014, 09:36 PM
Deveno
Re: prime numbers
Quote:

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$).
• Aug 4th 2014, 03:56 PM
dennydengler
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)
• Aug 6th 2014, 07:15 AM
SlipEternal
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.