SHOW K ? N , (2^K) +1 PRIME => then K is a power of 2 . please post the correct
ID: 2982738 • Letter: S
Question
SHOW K ? N , (2^K) +1 PRIME => then K is a power of 2 .
please post the correct answer with step by step solution , otherwise i will not give you 4 or 5 stars
plase read the question carefully whatever i asked for answer . othewise there is no need to waste your time .
Explanation / Answer
I gave a general case taking a and n...and also proving a is even and n is power of 2if a^n + 1 is prime, show that a is even and that n is a power > of 2. If n is not a power of two, then it has an odd prime factor m. So we can write n = m*r where we know for sure that m is odd. Since m is odd, we can write m = 2*k + 1 for some integer k. Thus n = 2*k*r + r Now exhibit a nontrivial factorization of a^n + 1: a^n + 1 = a^(2*k*r + r) + 1 = (a^r + 1) * (a^(2*k*r) - a^(2*k*r - r) + a^(2*k*r - 2*r) - ... + a^(2*r) - a^r + 1) To see that a has to be even note that if a were odd, then we could write: a = 1 mod 2. We know that n has to be a power of two, so n is even. So we can write n = 2*q for some integer q. Then a^n = a^(2*q) = 1^(2*q) = 1 mod 2. So if a is odd and n is even, a^n will always be odd. Then a^n + 1 will always be even and hence cannot be prime. So if a^n + 1 is to be prime, we cannot have a odd. I hope this helps. please help
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.