# Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

364 questions
Filter by
Sorted by
Tagged with
1 vote
42 views

### Miller-Rabin primality test final decision.

I feel like this question is more about math than, programming but it will include some simple code for the Miller-Rabin test (in scheme-lisp). ...
1 vote
115 views

### 23 and arithmetic progression

Starting at prime $23$, $$23 + 3 \cdot n \cdot(n+1)$$ is prime for $n=1$ to $21$. Is there a starting prime with more successes? Does this suggest that $23$ from $n=1$ to $1000$ would have the ...
90 views

### Combining strong pseudoprime test to base 2 and an Elliptic Curve test

I read Kubra Nari, Enver Ozdemir and Neslihan Aysen Ozkirisci: Strong pseudoprimes to base 2, in The Ramanujan Journal, 2022-04-26 (paywalled¹). Compared to a free earlier version at arXiv, the text ...
454 views

### Primality testing with binomial coefficients

Here is what I observed : Let $n$ be a natural number greater than 2. Let $A = 2\cdot\binom{3n+1}{n}-\binom{3n}{n-1}+\binom{3n-1}{n-2}$ Let $p=2n+1$ $p$ is prime iff $A \equiv 2 \pmod{p}$ You can run ...
92 views

### Randomized algorithm for finding a prime number between $n$ and $2n$

I have already seen some threads conjecturing that there is at least one prime between $n$ and $2n$. I am given an exercise, where I have relaxed this conjecture to the assumption that between $n$ and ...
31 views

### Asymptotic probability of prime divisors

I was curious about methods of finding primes. One method is to keep a list of the first $n$ primes, then check if the input modulo any prime less than its square root is zero. If none of those primes ...
123 views

### Primality test based on the properties of Pascal Triangle sum of a given row

I will list the properties of a row of Pascal triangle that will be used in the test. 1-Every number of a given row $n$ is divisible by the row number $n$ if the row number is a prime except of course ...
75 views

### A question on (trigonometric) prime counting function and twin prime counting function

Consider the following sum: $$S(t)=\sum_{n=5}^t\sin^2\left(\frac{π\Gamma(n)}{2n}\right)$$ As we can see this approximates $π(t)$ i.e. prime counting function pretty well. For details visit this paper ...
61 views

### Tweaking Fermat's primality test - Why does it work and should I expect different results?

Fermat's primality test states that for any $p$ as a positive odd integer, IF: $$a^{{p-1}}\equiv 1{\pmod {p}}$$ or in a different way: $$a^{{p}}-a\equiv 0{\pmod {p}}$$ THEN $p$ is probably prime. ...
53 views

1 vote
43 views

### Is number of prime factors in P?

We know primality is in P which gives an answer for all prime numbers that the number of prime factors of a prime number is 1. Is there an algorithm in P that would give answers for composite numbers ...
86 views

### How to repair this false statement about idoneal numbers?

In the german wikipedia , I found this site about idoneal numbers. The mentioned statement is false : $D=1848$ is an idoneal number and $m=1849$ is an odd number. $x^2+1848y^2=1849$ has only one ...
64 views

1 vote
86 views

### How does the AKS algorithm work?

I looked at the article of AKS in wikipedia (https://en.wikipedia.org/wiki/AKS_primality_test) and I don't understand how can I do the last level in a polynomial time (relatively to the number of ...
77 views

### Simple primality test

I am an amateur and have been doing some number theory for fun, so I apologize if my post is absolutely trivial:) I have been playing with primality tests and I thought of the following method: Pick ...
1 vote
59 views

### Odd prime divisor of $3x^2+y^2$ (where $x$, $y$ are relatively prime) is again of the same form

Euler proved that any prime divisor $\neq2$ of an integer of the form $3x^2+y^2$ is again of the same form. I know there are proofs available using quadratic reciprocity. I was curious to know ...
45 views

### if such counter example to Lehmer's totient problem exists then could we have more counter examples?

Lehmer's totient problem asks whether there is any composite number $n$ such that Euler's totient function $φ(n)$ divides $n − 1$. which it is unsolved problem or we may reformulate that question as : ...
### Primality test for specific class of $N=12k \cdot 5^n+1$
Can you prove or disprove the following claim: Let $P_m(x)=2^{-m}\cdot\left(\left(x-\sqrt{x^2-4}\right)^m+\left(x+\sqrt{x^2-4}\right)^m\right)$ . Let $N= 12k \cdot 5^{n} + 1$ where $k$ is an odd ...