Articles of primality test

Is there a Lucas-Lehmer equivalent test for primes of the form ${3^p-1 \over 2}$?

I’m reviewing the cyclotomic form $f_b(n)= {b^n-1 \over b-1}$ for various properties to extend an older treatize of mine on that form. With respect to primality there is the Lucas-Lehmer-test for primeness of $f_2(p)$ where of course $p$ itself must be a prime. I was now looking, whether I can say some things for primes […]

pseudo-primality and test of Solovay-Strassen

Let $n$ be an odd integer, we say that $n$ is $a$-pseudoprime if $gcd(a,n)=1$ and : $$\begin{pmatrix}\frac{a}{n}\end{pmatrix}=a^{\frac{n-1}{2}}\text{ mod } n $$ Euler’s criterion states that if $n$ is not prime, then at most half of the elements $a$ in $\frac{\mathbb{Z}}{n\mathbb{Z}}^*$ are such that $n$ is $a$-pseudoprime. Now I would like to know if we can […]

Primality of $n! +1$

I came across with a problem where I was required to examine primality of $n! +1$ (17! + 1 was the actual number). Although Wilson’s Theorem could be manipulated for determining primality of $n! + 1$ when $n + 1$ is a prime and $n! – 1$ when $n + 2$ is a prime, it […]

Will anyone check my primality test?

The proof is very straightforward and simple. We all know that all prime numbers have a last digit of 1, 3, 7 or 9, and I found that any composite number with a last digit of 1,3,7 or 9 is a product of two numbers having a last digit of 1,3,7 or 9. It can’t […]

Primality test for Proth numbers using Fibonacci numbers

How to prove or disprove the claim given below ? Let $P_j(x)=2^{-j}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{j}+\left(x+\sqrt{x^2-4}\right)^{j}\right)$, where $j$ and $x$ are nonnegative integers. Let $N=k \cdot2^m+1$ with $k$ odd , $0<k<2^m$ and $m>2$ . Let $F_n$ be the nth Fibonacci number and let $S_i=S_{i-1}^2-2$ with $S_0=P_k(F_n)$ , then $N$ is prime iff there exists $F_n$ for which $S_{m-2} […]

How to either prove or disprove if it is possible to arrange a series of numbers such the sum of any two adjacent number adds up to a prime number

I’m wondering if it’s possible to write a theorem to prove or disprove the possibility of arranging a sequence of numbers (1,2,…n) such that the sum of any two numbers adds up to a prime number. An Example: Input: Say n=7. The sequence is 1,2,3,4,5,6,7 Output: 7,6,5,2,1,4,3 Here are a few numbers where a program […]

Conjectured primality test

Can you provide a proof or a counterexample for the following claim : Let $n$ be a natural number , $n>2$ and $n \neq 9$ . Then $n$ is prime if and only if $\displaystyle\sum_{k=1}^{n-1}\left(2^k-1\right)^{n-1} \equiv n \pmod{2^n-1}$ You can run this test here . I was searching for a counterexample using the following two […]

Prime divisibility in a prime square bandtwidth

I am seeking your support for proving (or fail) formally the following homework: Let $p_j\in\Bbb P$ a prime, then any $q\in\Bbb N$ within the interval $p_j<q<p_j^2$ is prime, if and only if all: $$p_{i}\nmid q$$ with $1\le i<j$ There should be a simple sieving argument behind of this that I can not fish. I hope […]

Miller-Rabin-Test : Why can we be $100\%$ certain after $4$ tests for $p=13$?

I have question about a homework. The question is: Why can we be $100\%$ sure after $4$ tests for the special case of $p=13$? I don’t get it. I have a formula that states, that every test increases certainty by $\left(\frac14\right)^k$, where $k$ is the number of tests. So after $4$ tests I get around […]

Chebyshev Polynomials and Primality Testing

Let $T(n,x)$ be the nth Chebyshev polynomial of the first kind and let $U(n-1,x)$ the $(n-1)$th Chebyshev polynomial of the second kind. Would any one kindly help show that 1) $n$ is prime iff $T(n,x)$ is irreducible in $\mathbb{Z}[x]$. 2) $n$ is prime iff $U(n-1,x)$, expressed in powers of $(x^2-1)$, is irreducible in $\mathbb{Z}[x]$. Many […]