Return to Question

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes.

If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \mid \phi(n) $ (verified up to $x \le 2\cdot 10^6$). Setting $p$ to $7$, we get only two values of $x$; $x=7$ and $x = 281$.

If $x$ is allowed to take composite values, it appears there are infinitely many $x$ such that $x \mid \phi(n)$. Therefore, the following Conjecture is reasonable.

Conjecture 1

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes. For a fixed odd prime $p$, there are finitely many primes $x$ such that $x \mid \phi(n) $ with $n$ composite.

If Conjecture 1 is true, then, for a fixed prime $p$, there exists an upper bound $x_\text{max}$ such that $x \nmid \phi(n) $ for all $x>x_\text{max} $ with $n$ composite.

If Conjecture 1 is true, Theorem 1 gives a fast primality test for integers $x^{p-1}+x^{p-2}+\dotsb + x+1$ with $x > x_\text{max}$.

Theorem 1

Assuming Conjecture 1. Let $n =x^{p-1}+x^{p-2}+\dotsb + x+1$ where $x$ and $p$ are odd primes with $x>x_\text{max}$. If there exists a positive integer $b$ such that $b^{n-1} \equiv 1 \pmod n$ and $b^{(n-1)/x} \not\equiv 1 \pmod n$ then $n$ is prime.

Note: As $x$ is prime then $x \mid \phi(n) $ implies $n = (ux+1)(vx+1)$ for some non negative integers $u$, $v$ with $ux+1$ prime. It can also be shown that $n = (sp+1)(tp+1)$ for some non negative integers $s$, $t$ with $sp+1$ prime. And from this post Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$, if $ux+1 \mid n$ then $ux+1 \mid \frac{ u^{p}+1} {u+1}$. Perhaps these observations might be useful in proving Conjecture 1 and establishing $x_\text{max}$.

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes.

If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \mid \phi(n) $ (verified up to $x \le 2\cdot 10^6$). Setting $p$ to $7$, we get only two values of $x$; $x=7$ and $x = 281$.

If $x$ is allowed to take composite values, it appears there are infinitely many $x$ such that $x \mid \phi(n)$. Therefore, the following Conjecture is reasonable.

Conjecture 1

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes. For a fixed odd prime $p$, there are finitely many primes $x$ such that $x \mid \phi(n) $ with $n$ composite.

If Conjecture 1 is true, then, for a fixed prime $p$, there exists an upper bound $x_\text{max}$ such that $x \nmid \phi(n) $ for all $x>x_\text{max} $ with $n$ composite.

If Conjecture 1 is true, Theorem 1 gives a fast primality test for integers $x^{p-1}+x^{p-2}+\dotsb + x+1$ with $x > x_\text{max}$.

Theorem 1

Assuming Conjecture 1. Let $n =x^{p-1}+x^{p-2}+\dotsb + x+1$ where $x$ and $p$ are odd primes with $x>x_\text{max}$. If there exists a positive integer $b$ such that $b^{n-1} \equiv 1 \pmod n$ and $b^{(n-1)/x} \not\equiv 1 \pmod n$ then $n$ is prime.

Proof. Assuming Conjecture 1, we have $ x \mid \phi(n) $ if and only if $n$ is prime. Assume $n$ is composite. Using the properties of order of an integer, one can deduce that $ord_nb \mid (n-1) /x$. It follows that if $n$ is composite then $b^{(n-1)/x} \equiv 1 \pmod n$, contradicting our hypothesis. Therefore $n$ must be prime.

Note: As $x$ is prime then $x \mid \phi(n) $ implies $n = (ux+1)(vx+1)$ for some non negative integers $u$, $v$ with $ux+1$ prime. It can also be shown that $n = (sp+1)(tp+1)$ for some non negative integers $s$, $t$ with $sp+1$ prime. And from this post Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$, if $ux+1 \mid n$ then $ux+1 \mid \frac{ u^{p}+1} {u+1}$. Perhaps these observations might be useful in proving Conjecture 1 and establishing $x_\text{max}$.

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes.

If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \mid \phi(n) $ (verified up to $x \le 2\cdot 10^6$). Setting $p$ to $7$, we get only two values of $x$; $x=7$ and $x = 281$.

If $x$ is allowed to take composite values, it appears there are infinitely many $x$ such that $x \mid \phi(n)$. Therefore, the following Conjecture is reasonable.

Conjecture 1

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes. For a fixed prime odd prime $p$, there are finitely many primes $x$ such that $x \mid \phi(n) $ with $n$ composite.

If Conjecture 1 is true, then, for a fixed prime $p$, there exists an upper bound $x_\text{max}$ such that $x \nmid \phi(n) $ for all $x>x_\text{max} $ with $n$ composite.

If Conjecture 1 is true, Theorem 1 gives a fast primality test for integers $x^{p-1}+x^{p-2}+\dotsb + x+1$ with $x > x_\text{max}$.

Theorem 1

Assuming Conjecture 1. Let $n =x^{p-1}+x^{p-2}+\dotsb + x+1$ where $x$ and $p$ are odd primes with $x>x_\text{max}$. If there exists a positive integer $b$ such that $b^{n-1} \equiv 1 \pmod n$ and $b^{(n-1)/x} \not\equiv 1 \pmod n$ then $n$ is prime.

Note: As $x$ is prime then $x \mid \phi(n) $ implies $n = (ux+1)(vx+1)$ for some non negative integers $u$, $v$ with $ux+1$ prime. It can also be shown that $n = (sp+1)(tp+1)$ for some non negative integers $s$, $t$ with $sp+1$ prime. And from this post Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$, if $ux+1 \mid n$ then $ux+1 \mid \frac{ u^{p}+1} {u+1}$. Perhaps these observations might be useful in proving Conjecture 1 and establishing $x_\text{max}$.

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes.

If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \mid \phi(n) $ (verified up to $x \le 2\cdot 10^6$). Setting $p$ to $7$, we get only two values of $x$; $x=7$ and $x = 281$.

If $x$ is allowed to take composite values, it appears there are infinitely many $x$ such that $x \mid \phi(n)$. Therefore, the following Conjecture is reasonable.

Conjecture 1

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes. For a fixed odd prime $p$, there are finitely many primes $x$ such that $x \mid \phi(n) $ with $n$ composite.

If Conjecture 1 is true, then, for a fixed prime $p$, there exists an upper bound $x_\text{max}$ such that $x \nmid \phi(n) $ for all $x>x_\text{max} $ with $n$ composite.

If Conjecture 1 is true, Theorem 1 gives a fast primality test for integers $x^{p-1}+x^{p-2}+\dotsb + x+1$ with $x > x_\text{max}$.

Theorem 1

Assuming Conjecture 1. Let $n =x^{p-1}+x^{p-2}+\dotsb + x+1$ where $x$ and $p$ are odd primes with $x>x_\text{max}$. If there exists a positive integer $b$ such that $b^{n-1} \equiv 1 \pmod n$ and $b^{(n-1)/x} \not\equiv 1 \pmod n$ then $n$ is prime.

Note: As $x$ is prime then $x \mid \phi(n) $ implies $n = (ux+1)(vx+1)$ for some non negative integers $u$, $v$ with $ux+1$ prime. It can also be shown that $n = (sp+1)(tp+1)$ for some non negative integers $s$, $t$ with $sp+1$ prime. And from this post Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$, if $ux+1 \mid n$ then $ux+1 \mid \frac{ u^{p}+1} {u+1}$. Perhaps these observations might be useful in proving Conjecture 1 and establishing $x_\text{max}$.

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes.

If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \mid \phi(n) $ (verified up to $x \le 2\cdot 10^6$). Setting $p$ to $7$, we get only two values of $x$; $x=7$ and $x = 281$.

If $x$ is allowed to take composite values, it appears there are infinitely many $x$ such that $x \mid \phi(n)$. Therefore, the following Conjecture is reasonable.

Conjecture 1

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes. For a fixed prime odd prime $p$, there are finitely many primes $x$ such that $x \mid \phi(n) $ with $n$ composite.

If Conjecture 1 is true, then, for a fixed prime $p$, there exists an upper bound $x_\text{max}$ such that $x \nmid \phi(n) $ for all $x>x_\text{max} $ with $n$ composite.

If Conjecture 1 is true, Theorem 1 gives a fast primality test for integers $x^{p-1}+x^{p-2}+\dotsb + x+1$ with $x > x_\text{max}$.

Theorem 1

Assuming Conjecture 1. Let $n =x^{p-1}+x^{p-2}+\dotsb + x+1$ where $x$ and $p$ are odd primes with $x>x_\text{max}$. If there exists a positive integer $b$ such that $b^{n-1} \equiv 1 \pmod n$ and $b^{(n-1)/x} \not\equiv 1 \pmod n$ then $n$ is prime.

Note: As $x$ is prime then $x \mid \phi(n) $ implies $n = (ux+1)(vx+1)$ for some non negative integers $u$, $v$ with $ux+1$ prime. It can also be shown that $n = (sp+1)(tp+1)$ for some non negative integers $s$, $t$ with $sp+1$ prime. And from this post Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$, if $ux+1 \mid n$ then $ux+1 \mid \frac{ u^{p+1}+1} {u+1}$. Perhaps these observations might be useful in proving Conjecture 1 and establishing $x_\text{max}$.

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes.

If $p$ is set to $5$, it appears $x=5$ is the only prime $x$ such that $n$ is composite and $x \mid \phi(n) $ (verified up to $x \le 2\cdot 10^6$). Setting $p$ to $7$, we get only two values of $x$; $x=7$ and $x = 281$.

If $x$ is allowed to take composite values, it appears there are infinitely many $x$ such that $x \mid \phi(n)$. Therefore, the following Conjecture is reasonable.

Conjecture 1

Let \begin{equation} n =x^{p-1}+x^{p-2}+\dotsb + x+1 \end{equation} where $x$ and $p$ are odd primes. For a fixed prime odd prime $p$, there are finitely many primes $x$ such that $x \mid \phi(n) $ with $n$ composite.

If Conjecture 1 is true, then, for a fixed prime $p$, there exists an upper bound $x_\text{max}$ such that $x \nmid \phi(n) $ for all $x>x_\text{max} $ with $n$ composite.

If Conjecture 1 is true, Theorem 1 gives a fast primality test for integers $x^{p-1}+x^{p-2}+\dotsb + x+1$ with $x > x_\text{max}$.

Theorem 1

Assuming Conjecture 1. Let $n =x^{p-1}+x^{p-2}+\dotsb + x+1$ where $x$ and $p$ are odd primes with $x>x_\text{max}$. If there exists a positive integer $b$ such that $b^{n-1} \equiv 1 \pmod n$ and $b^{(n-1)/x} \not\equiv 1 \pmod n$ then $n$ is prime.

Note: As $x$ is prime then $x \mid \phi(n) $ implies $n = (ux+1)(vx+1)$ for some non negative integers $u$, $v$ with $ux+1$ prime. It can also be shown that $n = (sp+1)(tp+1)$ for some non negative integers $s$, $t$ with $sp+1$ prime. And from this post Positive divisors of $P(x,n)=1+x+x^2+ \cdots + x^n$ that are congruent to $1$ modulo $x$, if $ux+1 \mid n$ then $ux+1 \mid \frac{ u^{p}+1} {u+1}$. Perhaps these observations might be useful in proving Conjecture 1 and establishing $x_\text{max}$.