Prove, 2^n×3k+1
- Thread starter LupikCz
- Start date
D
Deleted member 4993
Guest
As you posted it - the term in question is:
2^n * 3k + 1
Is that what you wanted? If not, please use parentheses to elaborate.
Please show us what you have tried and exactly where you are stuck.
Please follow the rules of posting in this forum, as enunciated at:
Please share your work/thoughts about this problem.
Your translation is very poor. Do you mean you are supposed to prove
[MATH]\text {Given that } k,\ n \in \mathbb Z^+ \text { and } 3k + 1 \text { is prime} \implies\\ (2^n * 3k) + 1 \text { is not prime.}[/MATH]But that simply is not true.
If k = 2, then 3k + 1 = 7, which is prime.
If n = 1, then 2^1 * 3k + 1 = 2 * 6 + 1 = 13, which is prime.
[MATH]\text {Given that } k,\ n \in \mathbb Z^+ \text { and } 3k + 1 \text { is prime} \implies\\ (2^n * 3k) + 1 \text { is not prime.}[/MATH]But that simply is not true.
If k = 2, then 3k + 1 = 7, which is prime.
If n = 1, then 2^1 * 3k + 1 = 2 * 6 + 1 = 13, which is prime.
I thought about that too. But that question is just plain idiotic.
D
Deleted member 4993
Guest
Lupik - you came back to visit the site/question ~8 hours ago - yet, you did not respond !!
It
The goal is to prove that you cant find any k for which whould ve this expression always prime number for all value of positive integer n.
You are not doing well on clarifying your question.
Is k restricted to positive integers?
Is the expression
[MATH]x = 2^n * (3k + 1)[/MATH] or [MATH]x = (2^n * 3k) + 1[/MATH]?
In the first case, x is clearly the product of two positive integers, and the proof is trivial.
In the second case, you cannot prove your proposition because it is FALSE!
For example, if n = 1 and k = 2
[MATH]x = (2^1 * 3 * 2) + 1 = 12 + 1 = 13, [/MATH] which is a PRIME.
Is k restricted to positive integers?
Is the expression
[MATH]x = 2^n * (3k + 1)[/MATH] or [MATH]x = (2^n * 3k) + 1[/MATH]?
In the first case, x is clearly the product of two positive integers, and the proof is trivial.
In the second case, you cannot prove your proposition because it is FALSE!
For example, if n = 1 and k = 2
[MATH]x = (2^1 * 3 * 2) + 1 = 12 + 1 = 13, [/MATH] which is a PRIME.
The expression is
[MATH]x=(2^n*3k)+1[/MATH]n is starting from zero and going to infinity and you have to show that you cant find positive integer k for which would all values of expression
n=1
[MATH](2^1*3k)+1[/MATH]n=2
[MATH](2^2*3k)+1[/MATH]...
n=infinity
make always a prime number
[MATH]x=(2^n*3k)+1[/MATH]n is starting from zero and going to infinity and you have to show that you cant find positive integer k for which would all values of expression
n=1
[MATH](2^1*3k)+1[/MATH]n=2
[MATH](2^2*3k)+1[/MATH]...
n=infinity
make always a prime number
Ahh i get it it now. Prove that
[MATH]\text {There is no positive integer k such that}\\ (2^n * 3k) + 1 \text { is prime for every positive integer } n.[/MATH]Consequently, my example was flawed.
[MATH]k = 2 \text { and } n = 2 \implies (2^n * 3k) + 1 = (4 * 6) + 1 = 25, \text { not prime.}[/MATH]
Do I finally have it?
Yeah you got it, I was thinking about this a lot and still I dont know how to prove that.
I have not found a proof either.
But if k = 1 and n = 1, x = 7
k = 1 and n = 2, x = 13
k = 1 and n = 3, x = 25 perfect square
k = 2 and n = 1, x = 13
k = 2 and n= 2, x = 25 perfect square
k = 2 and n = 3, x = 49 perfect square
k = 3 and n = 1, x = 19
k = 3 and n = 2, x = 37
k = 3 and n = 3, x = 73
k = 3 and n = 4, x = 137
k = 3 and n = 5, x = 289 perfect square
Those perfect squares look intriguing. (Of course, it may be a false clue.)
But if k = 1 and n = 1, x = 7
k = 1 and n = 2, x = 13
k = 1 and n = 3, x = 25 perfect square
k = 2 and n = 1, x = 13
k = 2 and n= 2, x = 25 perfect square
k = 2 and n = 3, x = 49 perfect square
k = 3 and n = 1, x = 19
k = 3 and n = 2, x = 37
k = 3 and n = 3, x = 73
k = 3 and n = 4, x = 137
k = 3 and n = 5, x = 289 perfect square
Those perfect squares look intriguing. (Of course, it may be a false clue.)
No, k does not have to be even because, as you have framed the question, we are dealing with
[MATH](2^n * 3k) + 1.[/MATH] The term in parentheses is even because it is stipulated that n > 0.
Last edited:
Consider [MATH]p=3k+1[/MATH] prime,
then [MATH](3k+1)2^n \equiv 0[/MATH] mod p
[MATH]3k(2^n)+2^n \equiv 0[/MATH] mod p
[MATH]3k(2^n)+1+2^n-1 \equiv 0[/MATH] mod p
Let [MATH]n=3k[/MATH]:
[MATH]3k(2^{3k})+1+2^{3k}-1 \equiv 0[/MATH] mod p (*)
Now [MATH]2^{3k}-1 \equiv 0[/MATH] mod p (by Fermat's Little Theorem, and the fact that [MATH]p=3k+1>2[/MATH]).
(Fermat's Little Theorem [MATH]\rightarrow 2^{p-1}-1\equiv 0[/MATH] mod p prime >2))
So (*) [MATH]\rightarrow 3k(2^{3k})+1 \equiv 0[/MATH] mod p
I.e. this is composite (since [MATH]>3k+1[/MATH])
then [MATH](3k+1)2^n \equiv 0[/MATH] mod p
[MATH]3k(2^n)+2^n \equiv 0[/MATH] mod p
[MATH]3k(2^n)+1+2^n-1 \equiv 0[/MATH] mod p
Let [MATH]n=3k[/MATH]:
[MATH]3k(2^{3k})+1+2^{3k}-1 \equiv 0[/MATH] mod p (*)
Now [MATH]2^{3k}-1 \equiv 0[/MATH] mod p (by Fermat's Little Theorem, and the fact that [MATH]p=3k+1>2[/MATH]).
(Fermat's Little Theorem [MATH]\rightarrow 2^{p-1}-1\equiv 0[/MATH] mod p prime >2))
So (*) [MATH]\rightarrow 3k(2^{3k})+1 \equiv 0[/MATH] mod p
I.e. this is composite (since [MATH]>3k+1[/MATH])
In fact we don't need [MATH]3k+1[/MATH] to be prime.
Prove that [MATH]\,\forall k\in \mathbb{Z^+}\hspace1ex \exists n: \, k(2^n)+1[/MATH] is composite
Obviously true for k=1 (e.g. n=3)
Consider k>1, then (a) [MATH]\exists[/MATH] p prime >2: [MATH]\,p|(k+1)[/MATH] or (b) [MATH]k+1=2^m[/MATH] for some [MATH]m>1[/MATH]
Taking the first case, (a):
[MATH](k+1)2^n \equiv0[/MATH] mod p
[MATH]k(2^n)+1 + 2^n -1 \equiv 0[/MATH] mod p
Let [MATH]n=p-1[/MATH][MATH]k(2^{p-1}) + 1 + 2^{p-1} -1 \equiv 0[/MATH] mod p
[MATH]2^{p-1}-1 \equiv 0[/MATH] mod p (since p>2)
[MATH]\therefore k(2^{p-1}) + 1 \equiv 0[/MATH] mod p
[MATH]k(2^{p-1}) + 1>2^p>p \hspace1ex \therefore k(2^{p-1})+1[/MATH] is composite.
Taking the second case, (b):
[MATH]k+1=2^m[/MATH] (m>1 since k>1) and we want to find n: [MATH]k(2^n)+1[/MATH] is composite, i.e. [MATH](2^m-1)(2^n)+1[/MATH] is composite.
[MATH](2^m-1)(2^n)+1 = 2^{m+n}-2^n+1[/MATH]
Let n=m+2
[MATH]2^{m+n}-2^n+1=2^{2(m+1)}-2(2^{m+1})+1\\ =(2^{m+1}-1)^2[/MATH]which is composite (m>1).
Prove that [MATH]\,\forall k\in \mathbb{Z^+}\hspace1ex \exists n: \, k(2^n)+1[/MATH] is composite
Obviously true for k=1 (e.g. n=3)
Consider k>1, then (a) [MATH]\exists[/MATH] p prime >2: [MATH]\,p|(k+1)[/MATH] or (b) [MATH]k+1=2^m[/MATH] for some [MATH]m>1[/MATH]
Taking the first case, (a):
[MATH](k+1)2^n \equiv0[/MATH] mod p
[MATH]k(2^n)+1 + 2^n -1 \equiv 0[/MATH] mod p
Let [MATH]n=p-1[/MATH][MATH]k(2^{p-1}) + 1 + 2^{p-1} -1 \equiv 0[/MATH] mod p
[MATH]2^{p-1}-1 \equiv 0[/MATH] mod p (since p>2)
[MATH]\therefore k(2^{p-1}) + 1 \equiv 0[/MATH] mod p
[MATH]k(2^{p-1}) + 1>2^p>p \hspace1ex \therefore k(2^{p-1})+1[/MATH] is composite.
Taking the second case, (b):
[MATH]k+1=2^m[/MATH] (m>1 since k>1) and we want to find n: [MATH]k(2^n)+1[/MATH] is composite, i.e. [MATH](2^m-1)(2^n)+1[/MATH] is composite.
[MATH](2^m-1)(2^n)+1 = 2^{m+n}-2^n+1[/MATH]
Let n=m+2
[MATH]2^{m+n}-2^n+1=2^{2(m+1)}-2(2^{m+1})+1\\ =(2^{m+1}-1)^2[/MATH]which is composite (m>1).