Questions tagged [pseudoprimes]
Pseudoprimes are composite numbers which pass some primality test - a property that is always true for prime numbers. This may be Fermat's Little Theorem for one base or many, or some other test.
155
questions
0
votes
0
answers
37
views
Show $65$ is an Euler-Jacobi pseudoprime to the base $b \iff b^{2} = \pm 1 \mod 65$
Say $(b,65) = 1$. I want to show that
$$65 \text{ is an Euler-Jacobi pseudoprime to the base }b \iff b^{2} = \pm 1 \mod 65$$
that is,
$$b^{(65-1)/2} = b^{32} \equiv \left( \frac{b}{65} \right) \mod 65 ...
- 3,940
1
vote
1
answer
30
views
Question about the proof that composite numbers are Euler pseudoprimes to at most half of their coprime bases [closed]
Euler pseudoprimes are composite numbers $n$ for which the congruence $$a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n} \right) \quad (mod \ n)$$ holds, where $\left(\frac{a}{n} \right)$ is the Jacobi ...
- 243
1
vote
1
answer
54
views
If $n$ is pseudo prime to $2 \in Z_n$, then $N = 2^n -1$ is a pseudo-prime to $2 \in Z_N$.
If $n$ is pseudo prime to $2 \in Z_n$, then $N = 2^n -1$ is a
pseudo-prime to $2 \in Z_N$.
Attempt: By definition, $n$ being a pseudoprime to $2$ in $Z_n$ means $2^{n-1} - 1 = nk$ for some integer $k$...
- 153
3
votes
0
answers
106
views
Poulet numbers of the form $3p$, where $p$ is a palindrome
A Poulet-number is a composite number $N$ satisfying $$2^{N-1}\equiv 1\mod N$$ A palindrome is a positive integer with a digit string in base $10$ which remains the same if it is written down ...
user1250659
1
vote
1
answer
67
views
If $n$ is a Poulet number then $n+2$ is not a Poulet number?
Consider Fermat pseudoprimes to base $2$, also called Sarrus numbers or Poulet numbers.
Inspired by prime twins it makes sense to consider :
Conjecture :
If $n$ is a Poulet number then $n+2$ is not a ...
- 16.4k
3
votes
0
answers
75
views
Must one factor in $(2m^2+1)(8m^2+1)$ be prime to get a Poulet-number?
A Poulet-number is a Fermat pseudoprime to base $2$ that is it is a composite number $N$ such that $$2^{N-1}\equiv 1\mod N$$ holds.
Let $m$ be a positive integer and consider $f(m)=(2m^2+1)(8m^2+1)$
...
- 85.1k
6
votes
1
answer
287
views
Who can prove or disprove this conjecture?
Let $m$ be a positive integer such that $p:=8m^2+1$ is prime.
Conjecture : We always have $$2^{2m^2}\equiv 1\pmod p$$
I could only establish $$2^{4m^2}\equiv 1\pmod p$$ following from Euler's ...
- 85.1k
0
votes
0
answers
40
views
3-pseudoprimes of the form $n!\pm 1$?
If $n\ge 3$ is an integer :
Can $N=n!-1$ or $N=n!+1$ , except $5!+1$ , satisfy $3^{N-1}\equiv 1\mod N$ , but nevertheless be composite , in other words can $n!-1$ or $n!+1$ , except $121$ , be a weak ...
- 85.1k
0
votes
0
answers
27
views
3-pseudoprimes of the form $2^n\pm 1$?
If $n\ge 2$ is an integer.
Can $N=2^n-1$ or $N=2^n+1$ be a weak 3-Fermat pseudoprime , in other words can $N$ satisfy $$3^{N-1}\equiv 1\mod N$$ and nevertheless be composite ?
For $2\le n \le 5\ 000$...
- 85.1k
5
votes
0
answers
73
views
Is $1105$ the only Poulet-number of the form $2^a+3^b$?
Conjecture : $1105$ is the only Poulet-number that can be written in the form $2^a+3^b$ with positive integers $a,b$
A Poulet-number is a composite number $N$ satisfying the congruence $2^{N-1}\equiv ...
- 85.1k
1
vote
0
answers
69
views
Are there more Teluop-numbers?
This is not a yet known terminology , but I suggest it for Poulet-numbers with the property that they give another Poulet-number , if the decimal expansion is written down in reverse order analogue to ...
- 85.1k
4
votes
0
answers
143
views
An alien gives you a sequence, claiming it is the $1000$ prime gaps starting from the $10^{100}$th prime gap. How to check if they are likely lying?
I read an article that describes how to distinguish between real and fake sequences of coin tosses, with good reliability: we should check the longest run of heads (in real sequences of length $n$, ...
- 25.7k
2
votes
0
answers
96
views
PRP testing algorithms
INTRODUCTION: (scroll down for the actual question)
I want to check the primality of large numbers (more than $100\ 000$ digits).
Moreover, I want to be able to eliminate the use of expensive (yes, in ...
- 2,305
1
vote
1
answer
106
views
Pseudo-primes with non-prime bases
Given an odd integer n ≥ 5, and a base 2 ≤ a ≤ n-2, $a^{n-1} = 1 \mod n$ whenever n is a prime, and whenever the result is not 1, n is composite. Plus composite numbers where the result is 1 are rare. ...
- 10.3k
1
vote
0
answers
93
views
Are the Poulet-numbers of the form $k^2+1$ all squarefree?
A Poulet-number $n$ is a weak Fermat-pseudoprime to base $2$ , in other words a composite number $n$ with the property $$2^{n-1}\equiv 1\mod n$$
The first $34$ poulet-numbers of the form $k^2+1$ (...
- 85.1k