Prove that 14^n+11 is never prime

Watch this thread
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Report Thread starter 9 months ago
#1
I'm trying to use an inductive argument, however I've gotten stuck at one part.

So for n=0, 14^{n}+11=12=4\cdot3 \implies not a prime number.

Suppose that 14^{n}+11 is not prime for some integer k \geq1. Let 14^{k}+11=q for q\in\mathbb{N}.

\implies 14^{k+1}+11=14(q-11)+11=q+13q-11\cdot13=q+13(q-11). We know q is not prime from above, and 13(q-11) cannot be prime as q-11=1 for this to be true, and if q-11=1 \implies q=12, however q=14^{k}+11 for k\geq1 \implies q\geq15, so q cannot equal 12. Therefore 13(q-11) is not prime for all q.

I'm up to this point, and then wanted to show that this value can never be prime, but showing that both q and 13(q-11) are never prime does not imply that their sum is never prime (8+9=17 but 8 and 9 are clearly not prime). So is there anyway I could carry on from here to show that their sum is never prime? My only thought is some sort of contradiction argument?

Edit: I think I have it. Suppose that q+13(q-11) is prime, so let q+13(q-11)=p for some prime p. \implies 14q=p+143\implies q|(p+143) as q|LHS. However, as we know q is odd (14^{k} will always be even, and an even + odd yields an odd number), an odd number must divide the RHS. But the only way we have an odd number on the RHS is if p is even, so p must equal 2. However this clearly cannot be true, so p is a prime\geq2. \implies RHS is even, and so we have a contradiction when we stated that q|RHS.

Hence q+13(q-11) is never prime, and it follows by induction this is true for all n\in\mathbb{N}. I hope this is correct.
Last edited by username53983805; 9 months ago
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report 9 months ago
#2
(Original post by username53983805)
I'm trying to use an inductive argument, however I've gotten stuck at one part.

So for n=0, 14^{n}+11=<font color="#C10300">15</font>=5\cdot3 \implies not a prime number.
Minor point: = 12

Edit: I think I have it. Suppose that q+13(q-11) is prime, so let q+13(q-11)=p for some prime p. \implies 14q=p+143\implies q|(p+143) as q|LHS. However, as we know q is odd (14^{k} will always be even, and an even + odd yields an odd number), an odd number must divide the RHS. But the only way we have an odd number on the RHS is if p is even, so p must equal 2. However this clearly cannot be true, so p is a prime\geq2. \implies RHS is even, and so we have a contradiction when we stated that q|RHS.

Hence q+13(q-11) is never prime, and it follows by induction this is true for all n\in\mathbb{N}. I hope this is correct.
Just becase an odd number divides the RHS, does not imply the RHS is odd, indeed the 14 on the LHS imples the RHS must be even.


An inductive proof would work, but it's considerably more complicated.

As a hint, look for specific factors in the sequence
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report 9 months ago
#3
Can't edit my previous post

But once you have an inductive proof, or even without it, you should be able to rewrite it more simply without the necessity of induction.
0
reply
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report Thread starter 9 months ago
#4
(Original post by ghostwalker)
Minor point: = 12



Just becase an odd number divides the RHS, does not imply the RHS is odd, indeed the 14 on the LHS imples the RHS must be even.


An inductive proof would work, but it's considerably more complicated.

As a hint, look for specific factors in the sequence
i have no clue where I got 15 from haha.

Why does the 14 on the LHS imply that the RHS must be even?

From terms in the sequence, I'm getting the fact that when n is odd, the final digit is always a 5 so can never be prime, and when n is even, there is always a factor of 3, and so can never be prime either. I now have to generalise this right?
Last edited by username53983805; 9 months ago
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report 9 months ago
#5
(Original post by username53983805)
i have no clue where I got 15 from haha.

Why does the 14 on the LHS imply that the RHS must be even?
Well 14 is even, 2|LHS, therefore 2|RHS

From terms in the sequence, I'm getting the fact that when n is odd, the final digit is always a 5 so can never be prime, and when n is even, there is always a factor of 3.
So, alternate terms are divisible by 3 and 5.

Now think in terms of modular arithmetic - and forget the induction.
0
reply
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report Thread starter 9 months ago
#6
(Original post by ghostwalker)
Well 14 is even, 2|LHS, therefore 2|RHS



So, alternate terms are divisible by 3 and 5.

Now think in terms of modular arithmetic - and forget the induction.
But could I not just argue that q|LHS so q|RHS ==> q|p and q|143, clear contradiction which lies within this so initial assumption is incorrect? (This wouldn't be assuming the RHS is odd)

Okay let me have a think
Last edited by username53983805; 9 months ago
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
Report 9 months ago
#7
(Original post by username53983805)
But could I not just argue that q|LHS so q|RHS ==> q|p and q|143
I think you know yourself that that doesn't follow.

a|(b+c)\not\Rightarrow a|b \text{ and } a|c


Edit: Should have said in previous post that consecutive terms are alternately divisible by 3 and 5, but am unable to edit it due to a TSR bug.
Last edited by ghostwalker; 9 months ago
0
reply
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report Thread starter 9 months ago
#8
(Original post by ghostwalker)
Well 14 is even, 2|LHS, therefore 2|RHS



So, alternate terms are divisible by 3 and 5.

Now think in terms of modular arithmetic - and forget the induction.
Think I've got it.

For even n, i.e n=2k for k\in\mathbb{N}, want to prove that 14^{n}+11\equiv0 (\mathrm{mod} 3).
14^{2k}+11=196^{k}+11\equiv 1^{k}+2 (\mathrm{mod} 3) \equiv0 (\mathrm{mod} 3) for all k\in\mathbb{N}. (I am not 100% sure about this though).

For odd n, i.e n=2m+1 for m\in\mathbb{N}, want to prove that 14^{n}+11\equiv0 (\mathrm{mod} 5).
14^{2m+1}+11=14\cdot196^{k}+11\equiv -1\cdot1^{k}+1\equiv0 (\mathrm{mod} 5) for all m\in\mathbb{N}.

Again I am not sure about the validity of these proofs
Last edited by username53983805; 9 months ago
0
reply
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9
Report Thread starter 9 months ago
#9
(Original post by ghostwalker)
I think you know yourself that that doesn't follow.

a|(b+c)\not\Rightarrow a|b \text{ and } a|c
oh yes I just realised how stupid that was of me...
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10
Report 9 months ago
#10
(Original post by username53983805)
Think I've got it.

For even n, i.e n=2k for k\in\mathbb{N}, want to prove that 14^{n}+11\equiv0 (\mathrm{mod} 3).
14^{2k}+11=196^{k}+11\equiv 1^{k}+2 (\mathrm{mod} 3) \equiv0 (\mathrm{mod} 3) for all k\in\mathbb{N}. (I am not 100% sure about this though).

For odd n, i.e n=2m+1 for m\in\mathbb{N}, want to prove that 14^{n}+11\equiv0 (\mathrm{mod} 5).
14^{2m+1}+11=14\cdot196^{k}+11\equiv -1\cdot1^{k}+1\equiv0 (\mathrm{mod} 5) for all k\in\mathbb{N}.

Again I am not sure about the validity of these proofs
They look fine. In your last line just decide whether you're going with "m" or "k".

And you can finish with a summary line of some description.
0
reply
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11
Report Thread starter 9 months ago
#11
(Original post by ghostwalker)
They look fine. In your last line just decide whether you're going with "m" or "k".

And you can finish with a summary line of some description.
Thank you for your help, I must say this method is much nicer.

Out of curiosity, would there of been any way I could of proceeded in my original attempted solution to prove that q+13(q-11) was never prime, as that seemed to be all I needed to finish the proof.
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#12
Report 9 months ago
#12
(Original post by username53983805)
Out of curiosity, would there of been any way I could of proceeded in my original attempted solution to prove that q+13(q-11) was never prime, as that seemed to be all I needed to finish the proof.
Don't know, but I have grave doubts. q being composite (and odd) is insufficient to prove q+13(q-11) is not prime, e.g. q=15, gives 67, a prime, in the formula. So, you'd need to use some other information you know or can deduce.
0
reply
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#13
Report Thread starter 9 months ago
#13
(Original post by ghostwalker)
Don't know, but I have grave doubts. q being composite (and odd) is insufficient to prove q+13(q-11) is not prime, e.g. q=15, gives 67, a prime, in the formula. So, you'd need to use some other information you know or can deduce.
oh okay
Last edited by username53983805; 9 months ago
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest

Y13s: How will you be receiving your A-level results?

In person (79)
67.52%
In the post (5)
4.27%
Text (15)
12.82%
Something else (tell us in the thread) (18)
15.38%

Watched Threads

View All