The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

Prove that 14^n+11 is never prime

I'm trying to use an inductive argument, however I've gotten stuck at one part.

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

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

  ⟹  14k+1+11=14(q−11)+11=q+13q−11⋅13=q+13(q−11)\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  ⟹  q=12q-11=1 \implies q=12, however q=14k+11q=14^{k}+11 for k≥1  ⟹  q≥15k\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)q+13(q-11) is prime, so let q+13(q−11)=pq+13(q-11)=p for some prime p.   ⟹  14q=p+143  ⟹  q∣(p+143)\implies 14q=p+143\implies q|(p+143) as q∣LHSq|LHS. However, as we know q is odd (14k14^{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≥2\geq2.   ⟹  \implies RHS is even, and so we have a contradiction when we stated that q|RHS.

Hence q+13(q−11)q+13(q-11) is never prime, and it follows by induction this is true for all n∈Nn\in\mathbb{N}. I hope this is correct.
(edited 2 years ago)
Original post by username53983805
I'm trying to use an inductive argument, however I've gotten stuck at one part.

So for n=0,
Unparseable latex formula:

14^{n}+11=[color="#C10300"]15[/color]=5\cdot3 \implies

not a prime number.


Minor point: = 12


Edit: I think I have it. Suppose that q+13(q−11)q+13(q-11) is prime, so let q+13(q−11)=pq+13(q-11)=p for some prime p.   ⟹  14q=p+143  ⟹  q∣(p+143)\implies 14q=p+143\implies q|(p+143) as q∣LHSq|LHS. However, as we know q is odd (14k14^{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≥2\geq2.   ⟹  \implies RHS is even, and so we have a contradiction when we stated that q|RHS.

Hence q+13(q−11)q+13(q-11) is never prime, and it follows by induction this is true for all n∈Nn\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
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.
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?
(edited 2 years ago)
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.
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
(edited 2 years ago)
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)⇏a∣b and a∣ca|(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.
(edited 2 years ago)
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=2kn=2k for k∈Nk\in\mathbb{N}, want to prove that 14n+11≡0(mod3)14^{n}+11\equiv0 (\mathrm{mod} 3).
142k+11=196k+11≡1k+2(mod3)≡0(mod3)14^{2k}+11=196^{k}+11\equiv 1^{k}+2 (\mathrm{mod} 3) \equiv0 (\mathrm{mod} 3) for all k∈Nk\in\mathbb{N}. (I am not 100% sure about this though).

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

Again I am not sure about the validity of these proofs
(edited 2 years ago)
Original post by ghostwalker
I think you know yourself that that doesn't follow.

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

oh yes I just realised how stupid that was of me...
Original post by username53983805
Think I've got it.

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

For odd n, i.e n=2m+1n=2m+1 for m∈Nm\in\mathbb{N}, want to prove that 14n+11≡0(mod5)14^{n}+11\equiv0 (\mathrm{mod} 5).
142m+1+11=14⋅196k+11≡−1⋅1k+1≡0(mod5)14^{2m+1}+11=14\cdot196^{k}+11\equiv -1\cdot1^{k}+1\equiv0 (\mathrm{mod} 5) for all k∈Nk\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.
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)q+13(q-11) was never prime, as that seemed to be all I needed to finish the proof.
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)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)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.
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)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
(edited 2 years ago)

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you