An algorithm for determining whether an input number is prime.

learn more… | top users | synonyms

4
votes
1answer
77 views

Some heuristics about the Pisano Period, primes and Fibonacci primes. What reasons are behind them?

I started to read about the Pisano Period, $\pi(n)$, applied to the classic Fibonacci sequence and made some simple tests looking for possible properties of the sequence. I have observed the following ...
1
vote
2answers
54 views

Prove that $τ(m^n)$ and $n$ are coprime $(m,n ∈ N^+)$

We have that $τ(n)=\sum_{d|n} 1$ is the number of dividers of n. Dividers of $m^n$ are $1,m,m^2,...,m^n$ then we have that $τ(m^n)=n+1$. Is this correct so far? Now we must prove that $τ(m^n)$ and ...
1
vote
1answer
32 views

How many times do I loop Solovay--Strassen primality test

First, I am aware of this former thread: math.stackexchange Yet it doesn't answer my question. If I want to check if an integer $n$ is prime using the Solovay--Strassen test, how many times do I ...
2
votes
1answer
104 views

Leibniz theorem : A natural number $p> 2$ is prime iff $(p - 2)!-1 \equiv 0 \pmod p$.

I thought of using Wilson's theorem for the proof. First we have by Wilson's theorem $$(p - 1)!+1 \equiv 0 \pmod p$$ We can write this as $$(p - 2)!(p-1)+1 \equiv 0 \pmod p$$ $$(p - ...
0
votes
0answers
21 views

If, for some odd integer $n$, $P_n$ is the set of all bases $b$ in which $n$ passes a Fermat test, find the order of $P_n$.

I'm in a fourth year number theory course. The final exam is in two days and I can't figure out where to start with this question. It says to prove that $\operatorname{ord}(P_n) := \prod_{p\mid n} ...
2
votes
1answer
43 views

Why it is so difficult to perform primality test on huge fermat numbers?

I am not good in computer programming at all, but I know that it will take a lot of times to perform primality test on huge numbers (10 million or billion of digits). But I particularly get interested ...
2
votes
2answers
75 views

Miller-Rabin primality test for $2^{32}+1$

How can I prove that $2^{32}+1$ is composite number using Miller-Rabin primality test? I can't find a solution which verify the hypothesis of theorem.
2
votes
0answers
23 views

Conditions that suffice to show compositeness using Miller-Rabin test

I'm trying to sort out two descriptions of the Miller-Rabin test for primality: the one from Rabin's original paper and that from Wikipedia's article. Let $n$ be the number we wish to test, and let ...
0
votes
1answer
20 views

Probability of an aleatory experiment conducted $n$ times

What is the probability of an aleatory experiment conducted $n$ times? For example, say we choose randomly a number $x$ from a known interval, which happens to contain some certain kind of numbers ...
1
vote
1answer
34 views

Could Miller-Rabin primality test give false negative?

Could Miller-Rabin primality test give false negative, for example when test prime number and gives it as composite? I know that it could give false positive (giving composite number as prime), but ...
4
votes
1answer
68 views

Why is $\gcd(2^p + 1,3^p + 1) = 1$?

Let $p$ be an odd prime. Why is $\gcd(2^p + 1,3^p + 1) = 1$ ? I tried using fermat's little and $\gcd(a+b,a) = gcd(a,b)$ but without succes. I can make a statistical argument that suggests there are ...
0
votes
1answer
39 views

Generating false positives to the Rabin-Miller primality test

For what composite numbers $x$ will $a^{x-1} \equiv 1 \pmod x$ for $a \in [2,n]$? Can we generate $x$s that give false positives to the Rabin-Miller test for the first, say 10, consecutive integers ...
1
vote
0answers
34 views

Prove that a set of numbers can never consist of prime numbers

I noticed that for any integer $n>0$, $14^n+11$ would not be prime for up to $n=4$. Does this hold for all $n$? Is there a way to prove this or is this something that only works for some $n$?
5
votes
1answer
75 views

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$ ...
3
votes
2answers
97 views

Understanding Carmichael Number

A Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation $$a^{n-1} \equiv 1 \pmod n$$ $\forall a \in \mathbb Z_n$ such that $\gcd(a, n) = 1$ Wiki says ...
5
votes
2answers
70 views

Checking primality for $2 \uparrow \uparrow n + 3 \uparrow \uparrow n$

Is there a clever way to test primality for $$2 \uparrow \uparrow n \quad + \quad 3 \uparrow \uparrow n$$ where $n \gt 3$? (Not surprisingly, I got stuck after that) For $n \le 3$ we get: $$ ...
2
votes
2answers
57 views

Why does Miller-Rabin algorithm check for perfect powers?

I was reading the following version of the Miller-Rabin algorithm: it can also be found on page 6 of the following notes. The first if statement checks wether the input $n$ is a perfect power. i.e. ...
5
votes
1answer
39 views

Existence of a prime in between two integers, of which the larger integer is divisible by all prime divisors of the smaller integer.

Let $a$, $b \in \mathbb{N}$ and $3 < a < b$. Suppose all prime divisors of $a$ divide $b$ and all prime divisors of $b$ less than $a$ also divide $a$. Does there always exist a prime $p$ such ...
0
votes
0answers
48 views

A program for Primality Test for very large numbers

I need to test if a number is a prime number. Is there any program to test very large numbers like the biggest one with 17,425,170 digits ? I know about the Great Internet Mersenne Prime Search ...
3
votes
1answer
301 views

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{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)~ , \text{where}~ m ~\text{and}~ x ...
1
vote
3answers
89 views

Fermat primality test $\gcd$ condition and carmichael numbers

Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having): By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 ...
1
vote
2answers
145 views

Primality of $2^{255}-19$

I need a test for primality that I apply to $2^{255}-19$ (which is claimed to be prime) and certify to be correct with the ACL2 theorem prover. This means that I must be able to code the test in ...
0
votes
0answers
157 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
-3
votes
1answer
66 views

Rabin-Miller compositeness

Find a witness Rabin-Miller of compositeness of $n=25$ Can anyone explain and show me a way on how to solve this question?and generally how to find witness Rabin-Miller
5
votes
0answers
160 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers ...
0
votes
1answer
41 views

Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n I found this problem on internet and i am trying to find a solution ...
4
votes
1answer
69 views

Why are there not primality tests based on comparing the candidate $n$ with values of some $k \in [0,n]?$

I am learning basic number theory and as far as I could read, basically all the primality tests (or proven primality theorems) that are able to decide if a given $n$ is prime (or a special ...
5
votes
1answer
96 views

Non existence of absolute euler pseudoprimes

A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the ...
3
votes
0answers
77 views

Is there an advantage in using continued fractions for Catalan or Fibonacci-Lucas primality tests?

I am studying the basic theory about continued fractions and also reviewed here at MSE former questions to learn more. While reviewing the questions and answers, I found references to the Fibonacci ...
0
votes
0answers
36 views

Primality test similar to Pocklington

I'm working on a series of number theory proofs and I'm stumped on this one. The idea is to extend each result for the subsequent proof. I just succeeded in proving the following: Suppose $n > 1$. ...
1
vote
1answer
72 views

Fermat witness to compositeness of $n=21$

I have to find a Fermat witness to compositeness of $n=21$. I found this The Fermat compositeness test is a primality test based on the observation that by Fermat’s little theorem if $b^{n-1} ...
0
votes
0answers
41 views

Motivation for $r$ in AKS Primality Test

I've been reading up on the AKS primality test, and I understand the big ideas and proofs as they are pretty elementary number theory. I am confused about how to value of $r$ is selected. In the ...
7
votes
3answers
250 views

Conjectured Primality Test for $N=8\cdot 3^n-1$

Definition 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)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=8\cdot 3^n-1$ ...
2
votes
0answers
196 views

Primality Test for $N=2\cdot 3^n-1$

Definition 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)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=2\cdot 3^n-1$ such ...
12
votes
3answers
416 views

Mental Primality Testing

At a trivia night, the following question was posed: "What is the smallest 5 digit prime?" Teams (of 4) were given about a minute to write down their answer to the question. Obviously, the answer is ...
2
votes
4answers
57 views

Certificate of primality based on the order of a primitive root

Reading my textbook, it tells me that to prove $n$ is prime, all that is necessary is to find one of its primitive roots and verify that the order of one of these primitive roots is $n-1$. Now, why ...
0
votes
1answer
86 views

Is there a primality test based on the sum of squares of the first $n$ natural numbers $\sum_{x = 1}^{n} x^2$?

The Fibonacci and Catalan primality tests are based on the calculation of the congruences of those numbers versus the possible prime $n$ (the rules are different depending on the primality test), and ...
0
votes
0answers
45 views

How to simplify finite product?

I've got such equation: $$f(x) = (\sin(2 π x/2 - π / 2) + 1)(\sin(2 π x/3 - π / 2) + 1) \cdots (\sin(2 π x/(x-1) - π / 2) + 1)$$ I want to know if the function $f(x) = 0$ or not because this states ...
4
votes
4answers
166 views

Can we predict when a polynomial can take more than one perfect square value?

We consider only polynomial with integer coefficients. We know how to determine the first perfect square value but we don't know how to determine subsequent perfect square values except by testing ...
2
votes
0answers
52 views

Determine whether permutation of the digits of a number is prime

Given a number $m$ in decimal representation. I want to find a permutation of the digits of $m$, so it is prime. (Or output that there exists none) Do i have in the worst case check every possible ...
3
votes
1answer
144 views

New primality test, now what (publishing and proof)? [closed]

Over my research, I found a new relatively simple way to calculate whenever a number is prime or not. What's exciting is that it runs in $O(\log^2 n)$ running time (where $n$ is the number of digits ...
2
votes
2answers
79 views

How many Fermat tests are needed to verify a Carmichael number

If $n$ is a Carmichael number, then for all values $a$ such that $0<a<n$ (and $a \perp n$): $a^{n-1} \equiv 1 \mod n$ However, is it not necessary to check check all $a$ values because for a ...
6
votes
0answers
537 views

2015-related question: why are Lucas-Carmichael numbers named after Lucas?

Summary 2015 is a so called Lucas-Carmichael number. I believe (for reasons that I will explain below) that the 'Carmichael' in the name is a reference to ordinary Carmichael numbers and not to the ...
4
votes
1answer
195 views

Determining the starting value for primality test

This question is about Lucasian primality test for numbers of the form $N=3\cdot 2^n-1$ . There is a following statement in Wikipedia article : Lucas-Lehmer-Riesel test : "If $k = 3$ : if $n = 0$ ...
6
votes
0answers
74 views

How probable is that a randomly typed 47 digit odd integer is a prime?

So, I have been playing around with prime numbers, I have installed gmp and gmpy2 gmpy2 has ...
0
votes
2answers
28 views

Polynomial modulo n

http://en.wikipedia.org/wiki/AKS_primality_test How can I interpret what the "mod n" means? I have watched the Numberphile video on the AKS primality test, and based on that, I am assuming that ...
3
votes
2answers
169 views

Do we still need probabilistic primality testing methods for practical applications?

Probabilistic primality testing methods like Rabin Miller and Solovay Strassen, were created at the time when mathematicians were not sure whether there is a deterministic polynomial algorithm. After ...
0
votes
2answers
92 views

Make a prime number from specified number, by concatenating some more digits on its right?

I am given a number, I don't know whether it's prime or not. The algo says, For eg - Step 1 - Convert char to ints. (Hello - 72101108108111) Ascii values Step 2 - Make a large number. Convert char ...
3
votes
1answer
64 views

Finding a lower bound to the probability that a number will be shown to be composite?

Given the following method to decide whether a number $m$ is prime or not: Choose a random number $1<a<m-1$, and check whether $a^{m-1} = 1 \mod m$. If its equal, return true, otherwise - ...
4
votes
2answers
144 views

Bases required for prime-testing with Miller-Rabin up to $2^{63}-1$

This webpage (as well as Wikipedia) explains how one can use the Miller-Rabin test to determine if a number in a particular range is prime. The size of the range determines the number of required ...