# Tagged Questions

48 views

### Are there any primes that are never a factor of a Carmichael number?

Is there a prime number $p$ that $p > 2$, and in which $p$ is a never a factor of any Carmichael number $C_n$: (p ∤ $C_n$) Extended this to all numbers $m$, instead of just $p$, will prove the ...
62 views

### If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So ...
48 views

### Fast check of safe primes or Sophie Germain primes

If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$. In ...
45 views

### What's the best software for primality tests of huge numbers? (check if an integer is prime or not)

I just read an article about huge prime numbers (some with more than 10millions digits!) that are discovered using software that check if an integer is prime or not (primality test sofwares). What is ...
42 views

### How many $\overline{a}\in\left(\mathbb{Z}/91\mathbb{Z}\right)^\times$ pass the Fermat and Miller-Rabin primability tests?

Let $$\text{F}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Fermat primality test to base }a\right\}$$ and ...
1k views

### Is a cube root of a prime number rational?

The question is: if $P$ is prime is $P^{1/3}$ rational? I have been able to prove that if $P$ is prime then the square root of $P$ isn't rational (by contradiction) how would I go about the cube ...
107 views

### How to use Euler's primality test

I am trying to understand how Euler's primality test works. I use this paper as a guide. To summarize Euler's criterion Euler's criterion(in my uderstanding). For an integer $a$, and an odd prime ...
381 views

### 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 ...
44 views

### Finding errors in primality tests?

How do you know when a primality test generates a number that is not prime?
83 views

### Is my sieve generalisable?

I was curious about extending Euler's polynomial generator n^2 - n + 41 for n > 41, and looking for the simplest sieves. I examined the gaps between non-primes and found a set of simple sieves of the ...
2k views

### Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
66 views

### What is the well-known result used to prove primality of $n=2pq+1$ under certain conditions?

On Henri Lifchitz's website, we find: If $n=2pq+1$, $p$ and $q$ primes and $q>2p$, if there is an integer $a$ such $a^{n-1} \equiv 1 \pmod n$ and $\gcd(a^{2p}-1,n)=1$ then $n$ is prime. It is ...
32 views

### Primality Test with some condition

Given a prime number p, how can I quickly determine the primality of 10p+a, where a is an integer between 0 and 9? O(1) test is preferred Thanks!
149 views

### What is mod(a,b)?

I was reading the AKS Primality Test. AKS. I could not understand the line : $(x - a)^{n} = (x^{n} - a) \pmod{(n,x^{r}-1)}$ What is $\mod{(a,b)}$ in it ?
94 views

### Looking for a more efficient primality testing Algorithm than Miller-Rabin

I am looking for a practical probabilistic primality testing algorithm that is more superior than Miller-Rabin. By "more superior", I mean that the probability of giving the wrong answer is better ...
133 views

### Probability of 2 as a liar in the SPRP test - Miller-Rabin

I've used number-theoretic results for p(k, t) (e.g., DLP) to create a utility, mrtab, that generates the Miller-Rabin iterations (as a k-bit threshold table) required to satisfy a given ...
350 views

### Primality test square root of n

I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of $n$ from $2$ to $\sqrt n$, but look at this number: $$7551935939 = 35099 \cdot 215161$$ ...
80 views

### 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 ...
164 views

### Making fermat's little theorem for composite numbers the ultimate test.

It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem ...
213 views

### Miller-Rabin Primality Test

I am trying to work out the potential primality of 341 using the Miller-Rabin algorithm. Below is as far as I get, I'm not really sure where to go from there. I believe I am supposed to use modular ...
90 views

### How to test a real number a prime number [closed]

if $p^{1/n}$ where $p$ is a prime number and $n$ is an integer, will it be a prime number? should $n$ be prime? for example $\sqrt3^{1/3}$, $\sqrt3^{1/10}$ what is the algorithm to test a real ...
246 views

### Constructing arbitrary sized Miller-Rabin Primality Test Case Numbers

The Miller–Rabin (or Rabin-Miller) primality test is an algorithm that determines whether a given number is prime. Is it possible to construct a number that will pass an arbitrary number of ...
161 views

### What is this shortcut to determine primality?

I'm watching this, he says that David Slowinski discovered the biggest prime in 1984: $2^{132,049}$-1 and that it took 1 week on a Cray supercomputer: using some shortcut and that the absence of this ...
129 views

### Lucas' primality test == finding a primitive root?

I'm looking at some definitions of Lucas' primality test and as far as I can see the algorithm for the examples shown on most sites seem to just be "For some number $n$ if $n$ has a primitive root ...
112 views

### primes and patterns/representations

As we know that primes other than 2 and 3 can be expressible as: $p \equiv 1\pmod{6}$ or $p \equiv -1\pmod{6}$. In other words, 6|(p-1) or 6|(p+1). Or, p = 6h+1 or 6h-1. Now, for any integer h, ...
89 views

### Is This a Good Prime Sieve?

I have played around with deriving a Boolean IsPrime function. http://science.niuz.biz/boolean-t313980.html?s=5e8b6805a1b73daa7c1062fabbe74e90 I have found a simple method for deriving a single ...
141 views

### Is there an emirp greater than $10^{10006}+941992101 \times 10^{4999}+1$?

An emirp is a prime such that a distinct prime is formed when its digits are reversed. According to Wikipedia (and its references), the largest known emirp is \[p:=10^{10006}+941992101 \times ...