Proof for Challenge Question Number Theory Part 1 - Raghav Mukhija We need to show that if (x^n - 1)/(x - 1) is prime, then n must be prime. *Proof by Contradiction* (x^n - 1)/(x - 1) is prime. Assume n is not a prime number. Then n can be written as n=ab where a and b are integers greater than 1. x^n-1=x^ab−1=(x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) (x^n - 1)/(x - 1)= [ (x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) ]/[x-1] Here, [x−1] is less than or equal to either (x^a - 1) or (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1). Both(x^a - 1) and (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) are integers greater than 1, so (x^n - 1)/(x - 1) is a product of two non-trivial factors. Therefore, (x^n - 1)/(x - 1) is not prime. -- CONTRADICTION Hence proved that if (x^n - 1)/(x - 1) is prime, then n must be prime. (x^n - 1)/(x - 1) = 1+x+x^2 +⋯+x^(n−1) *Hence proved that if 1+x+x^2 +⋯+x^(n−1) is prime, then n must be prime.*
Proof for Challenge Question Number Theory Part 1 - Raghav Mukhija We need to show that if (x^n - 1)/(x - 1) is prime, then n must be prime. *Proof by Contradiction* (x^n - 1)/(x - 1) is prime. Assume n is not a prime number. Then n can be written as n=ab where a and b are integers greater than 1. x^n-1=x^ab−1=(x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) (x^n - 1)/(x - 1)= [ (x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) ]/[x-1] Here, [x−1] is less than or equal to either (x^a - 1) or (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1). Both(x^a - 1) and (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) are integers greater than 1, so (x^n - 1)/(x - 1) is a product of two non-trivial factors. Therefore, (x^n - 1)/(x - 1) is not prime. -- CONTRADICTION Hence proved that if (x^n - 1)/(x - 1) is prime, then n must be prime. (x^n - 1)/(x - 1) = 1+x+x^2 +⋯+x^(n−1) *Hence proved that if 1+x+x^2 +⋯+x^(n−1) is prime, then n must be prime.*
Proof for Challenge Question Number Theory Part 1 - Raghav Mukhija
We need to show that if (x^n - 1)/(x - 1) is prime, then n must be prime.
*Proof by Contradiction*
(x^n - 1)/(x - 1) is prime.
Assume n is not a prime number. Then n can be written as n=ab where a and b are integers greater than 1.
x^n-1=x^ab−1=(x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1)
(x^n - 1)/(x - 1)= [ (x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) ]/[x-1]
Here, [x−1] is less than or equal to either (x^a - 1) or (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1).
Both(x^a - 1) and (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) are integers greater than 1, so (x^n - 1)/(x - 1) is a product of two non-trivial factors.
Therefore, (x^n - 1)/(x - 1) is not prime. -- CONTRADICTION
Hence proved that if (x^n - 1)/(x - 1) is prime, then n must be prime.
(x^n - 1)/(x - 1) = 1+x+x^2 +⋯+x^(n−1)
*Hence proved that if 1+x+x^2 +⋯+x^(n−1) is prime, then n must be prime.*
assume is composite. n = pq, x^n - 1 / x - 1 = (x^n - 1)/(x^p - 1) * (x^p - 1)/(x - 1), which are both clearly integer > 1, so done.
Proof for Challenge Question Number Theory Part 1 - Raghav Mukhija
We need to show that if (x^n - 1)/(x - 1) is prime, then n must be prime.
*Proof by Contradiction*
(x^n - 1)/(x - 1) is prime.
Assume n is not a prime number. Then n can be written as n=ab where a and b are integers greater than 1.
x^n-1=x^ab−1=(x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1)
(x^n - 1)/(x - 1)= [ (x^a - 1)( x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) ]/[x-1]
Here, [x−1] is less than or equal to either (x^a - 1) or (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1).
Both(x^a - 1) and (x^{a(b-1)} + x^{a(b-2)} + … + x^a + 1) are integers greater than 1, so (x^n - 1)/(x - 1) is a product of two non-trivial factors.
Therefore, (x^n - 1)/(x - 1) is not prime. -- CONTRADICTION
Hence proved that if (x^n - 1)/(x - 1) is prime, then n must be prime.
(x^n - 1)/(x - 1) = 1+x+x^2 +⋯+x^(n−1)
*Hence proved that if 1+x+x^2 +⋯+x^(n−1) is prime, then n must be prime.*