# Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

334 questions
Filter by
Sorted by
Tagged with
37 views

### Primality test via Euler’s totient function [duplicate]

How can I prove the following theorem using Wilson’s theorem: Let n ≥ 2 be an integer. Show that n is prime if and only if $n|(φ(n)!+1$. The first direction is easy, but the other way I do not have an ...
62 views

### Primality test for specific class of $N=k \cdot 2^n+1$

Can you prove or disprove the following claim: Let $N=k \cdot 2^n+1$ be a natural number that is not a perfect square such that $2 \nmid k$ , $n>2$ . Let $c$ be the smallest odd prime number such ...
644 views

### $n$ is prime iff $\binom{n^2}{n} \equiv n \pmod{n^4}$?

Can you prove or disprove the following claim: Let $n$ be a natural number greater than two , then $$n \text{ is prime iff } \binom{n^2}{n} \equiv n \pmod{n^4}$$ You can run this test here. I have ...
65 views

### Every strong pseudoprime is an Euler-Jacobi pseudoprime to base $b$

Prove that every strong (i.e. Miller-Rabin) pseudoprime to base $b$ is also an Euler-Jacobi pseudoprime to base $b$ I am trying to prove the above but I am struggling. Any hints?
213 views

### A generalization of Hurwitz's theorem about prime numbers

Can you prove or disprove a generalization of Hurwitz's theorem about prime numbers given below? Theorem.(Hurwitz) Let $F_n(x)$ denote an irreducible factor of degree $\phi(n)$ of $x^n-1$. Then if ...
115 views

66 views

### How to check the primality of $2^n + 1$?

With Mersenne Numbers, if $M = 2^n - 1$ is prime, $n$ is prime. Is there a trick (may be similar to that of Mersenne) to check the primality of $2^n + 1$?
40 views

### How one can reformulate the sentence: $T_{n}(x)/x$ is irreducible over the integers

The motivation to this question can be found in: Chebyshev Polynomials and Primality Testing My question is: How one can reformulate the sentence: $T_{n}(x)/x$ is irreducible over the integers ...
43 views

### Why do we choose random bases for the Fermat primality test?

As in title, why do people usually choose random bases for the Fermat primality test as opposed to just using bases $2, 3, 4, ...$ in succession? Say we want to know if $N$ is prime/Carmichael or ...
155 views

### About how much time would it take to test the primality of a billion digit Mersenne number with a typical processor?

I'm wondering how long it might take to run a Lucas Lehmer primality test on a one billion digit Mersenne prime using a 3.0 ghz processor.
79 views

### Proof of Lehmann's primality test

I'm struggling to understand the details in the proof of Lehmann's primality test (Algorithm2 in the link). Explanations, and a more incremental walkthrough in general would be very appreciated. ...
84 views

### Primality testing when $n\equiv3\pmod{4}$ and $gcd(totient(n), (n-1)/2) = 1$

Euler proved that if $n$ is prime, $a^{\frac{n-1}{2}}\equiv \genfrac{(}{)}{}{}{a}{n}\pmod{n}$, which for primes is $1$ if $a$ is a quadratic residue mod $n$, $-1$ if $a$ is a non-quadratic residue mod ...
37 views

I've been reading a paper of Rabin and Shallit ("Randomized Algorithms in Number Theory"), which gives a brief sketch of an ERH-conditional algorithm to compute a representation of a positive integer $... 3answers 115 views ### Heuristic primality test with an offer$620 for a counterexample

There is a heuristic primality test which combine the Fermat test and the Fibonacci test (with an offer $620 for a counterexample):$(1)\quad 2^{p−1} \equiv 1 \pmod p(2)\quad f_{p+1} \equiv 0 \...
397 views

### time complexity of some specific system of $(n-3)/2$ linear equations with $(n-3)/2$ unknowns.
let take n a odd integer greater than 3 if I have to solve this system of $(n-3)/2$ linear equations with $(n-3)/2$ unknowns to find some propriety about the number n, here is formula for every ...