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

137 questions
Filter by
Sorted by
Tagged with
134 views

### Fermat's little theorem, Poulet numbers, Carmichael numbers, and primes

Fermat's primality test for base 2 permits Poulet numbers to pass the test, as follows: $(2^x - 2)/x$. Fermat's primality test in different bases will act as a sieve for eliminating most pseudo ...
51 views

### Fast primality testing for very large primes

I'm working on a project that requires me to find whether extremely large numbers are prime numbers or not. Of course, I've read how to find prime numbers and have come up with a very simple brute ...
41 views

### Show that if $p$ is a prime divisor of $n$ and we set $m = n/p$, then $n$ is a pseudoprime to the base $b$ if $b^{m−1} \equiv 1 \bmod p$

Show that if $p$ is a prime divisor of $n$ and we set $m = n/ p$, then $n$ is a pseudoprime to the base $b$ if $b^{m−1} \equiv 1 \bmod p$. (Hint: write $n = m(p−1 + 1)$) def: pseudoprime $n$ for ...
24 views

### Probable prime test maximum probability error

1 Suppose we have the following probable prime test for an integer $n$: Choose any integers $a$ and $b$ such that Jacobi$(a,n)=-1$ and $\gcd(b,n)=1$ [2] If $(x+b)^n = -x+b \mod (n,x^2-a)$, then $n$...
56 views

### is there any deterministic versions of fermat test except this one?

fermat test says : if $a^{N-1} \equiv 1 \pmod N$, then N is probably prime number, but according to pocklington primality test if: $3^{N-1} \equiv 1 \pmod N$, then N is proven prime, where $N=2p+1$...
52 views

### Can Cipolla algorithm be used as a primality test?

https://en.wikipedia.org/wiki/Cipolla%27s_algorithm describes the steps to compute a modular square root, assuming a prime modulus. The converse of this algorithm could be: considering a quadratic ...
73 views

### how to run fermat test on large numbers

fermat test is a primality test, says that: if $a^{N-1} \equiv 1\mod N$, then N in is probably prime, but I have searched for any program that allows me to run this test on large numbers (...
32 views

### Determine if N is a pseudoprime / strong pseudoprime

How can I conclude from the following table whether N=15841 is a pseudoprime and/or strong pseudoprime for the bases a=2, a=145, and a=789? Given is that 15840 = 2^5 * 495 So far I know that a ...
40 views

### Carmichael numbers of order $4$

Carmichael numbers are known to have the property $p-1 | N-1$ for all $p | N$. It is also easy to find numbers $N$ such that $p+1 | N+1$ for all $p | N$ (these numbers lead to strong lucas ...
45 views

77 views

### Proving that a Prime Power $p^{k}$ is a Divisor of $a^{p-1} - 1$

Let $n$ be a Fermat-pseudoprime with respect to $a$. Let $p$ be a prime divisor of $n$ and let $k\in\mathbb{Z}_{>0}$. Show that if $p^k\mid n$, then $p^k\mid (a^{p-1}-1)$. I tried showing this as ...
41 views

### Proving (pseudo)primality

Let $p$ be prime and let $d\in\mathbb{Z}_{>1}$ dividing $2^p-1$. Show that $d$ is prime or Fermat-pseudoprime with respect to 2. I'd like to prove this by showing that $p$ divides $d-1$. Because, ...
27 views

### Proving strong pseudoprimality

Let $n$ be a Fermat-pseudoprime with respect to 2. Show that $2^n-1$ is a strong pseudoprime with respect to 2. I tried solving the problem as follows. Since $n$ is a Fermat-pseudoprime with respect ...
28 views

20 views

### Properties of Poulet factors

What I want to prove is that given the following condition: There exists an $a$ and a corresponding $b$ such that $2^{ab}-2 \text{ mod}(ab) \equiv 0 |a,b\in \mathbb{Z}$ (Thus satisfying Fermat's ...
41 views

### Pseudoprime Generator Proof

I have a proof for a pseudoprime generator that I haven't been able to find elsewhere. Here it is: Fermat's Little Theorem proves that $2^{p}-2 \equiv 0 (\text{mod }p)$ where p is either a prime or ...
108 views

### Simplify convoluted $\text{prime}^*$ numbers sum formulae

The below is part of a formula I devised to calculate the sum of the squared reciprocals of all primes and pseudo-primes (pseudo according to Fermat's Little theorem.) However, the 4 sums are very ...
35 views

### When is $\frac{a^p+1}{a+1}$ a pseudoprime to base $b$?

Let $a$ and $b$ be postive integers greater than $1$ and $p$ be an odd prime. Is there an easy criterion whether the number $$N:=\frac{a^p+1}{a+1}$$ is a weak Fermat-pseudoprime to base $b$, in ...
64 views

### Fermat primality test for $a=n-1$

If we want to know if $n$ is prime, we can do the Fermat primality test: if $a^{n-1}\not\equiv 1 \mod n$, then $n$ is not prime. Now I often find that we choose therefore $a\in\{2,\ldots, n-2\}$. ...
59 views

### Lower bounds for totient function of a Carmichael number

Short version: I am wondering if there are any good bounds of the form $\phi(n) \geq f(n)\cdot n$ with $f(n)$ close to 1 for high $n$, optionally under the assumption that $n$ is a Carmichael number. ...
29 views

### Gaps and density of numbers consisting of sums of products of primes where the number of factors for each prime is itself prime

For the following set of numbers: $$\{ n \} =\sum_{i=1}^{\infty} b_i p_i^{p_{j_i}}$$ where each $b_i$ (b for binary) is either 1 or zero each $n$ in the set $\{ n \}$ has a unique set of $\{b_i\}$ ...
20 views

### Can $(x-1)(y+1)+xy$ be a Fermat-pseudoprime , when $x$ is a power of $2$ and $y$ a power of $10$?

Suppose, $m$ and $n$ are positive integers and $x=2^m$ and $y=10^n$. Can $$(x-1)(y+1)+xy$$ be a Fermat-pseudoprime to base $2$ ? For $m,n\le 200$, no such Fermat-pseudoprime exists.
37 views

### Weaker Goldbach's Conjecture: Is every number the sum of two pseudoprimes?

Here, pseudoprimes refer to composite pseudoprimes as well as primes. Can this be easily shown for Fermat Pseudoprimes? For Strong Pseudoprimes? For Pseudoprimes to a constant base? etc.
87 views

### Prove that an odd square cannot be a pseudoprime with both base 2 and base 3

Background: The Baillie PSW primality test 1 tests if the number is a square before the Selfridge parameter selection. The Mathematica implementation of PrimeQ does ...
94 views

### Are these the smallest Poulet-numbers above $10^{16}$ and $10^{17}\ \$?

A Poulet-number is a composite positive integer $\ N>1\$ satisfying the condition $$2^{N-1}\equiv 1\mod N$$ The numbers $$10^{16}+8\ 663\ 854\ 653$$ and $$10^{17}+209\ 045\ 665\ 633$$ are Poulet-...
35 views

### Is this a proper superset of Carmichael numbers?

While looking into the Lucas primality test I noticed an interesting thing. Using the following test* I discovered a sequence of numbers which, for lack of a better ...
113 views

### Was the number $3,317,044,064,679,887,385,961,981$ doublechecked?

In Wikipedia , Miller-Rabin-Test, it is mentioned that the smallest strong-Fermat pseudoprime to the prime-bases upto $41$ is $$3,317,044,064,679,887,385,961,981$$ Hence, every number smaller than ...
38 views

### Conjecture about congruences arising from a special semiprime

Let $k$ be a positive integer such that $p=2k+1$ and $q=4k+1$ are both prime. Consider the number $$N=pq$$ I proved that for every positive integer $a$ coprime to $N$ we have $$a^{N-1}\equiv 1\mod N$$ ...
46 views

### Finding Large Pseudoprimes with a Computer

I'm reading the book Prime and Programming and I'm stuck on one of the computer exercises. I'm checking for Fermat Pseudoprimes and I've written a program that works for reasonably small numbers, e.g....
50 views

52 views

### if $d$ divides $n$, why is $d^{n-1} \not\equiv 1 \pmod n$?

For the Fermat test it is stated that $a^{n-1} \equiv 1 \pmod n$ implies that $\gcd(a, n) = 1$ even when $n$ is not prime (the case for prime $n$ is obvious). I want to know why is this true. If I ...
380 views

### Do $n=2m+1$ and $\big(2^m\bmod(m\cdot n)\big)\in\{n+1,3n-1\}$ imply $n$ prime?

Do $n=2m+1$ and $\big(2^m\bmod(m\cdot n)\big)\in\{n+1,3n-1\}$ imply $n$ prime? Equivalently, for $n=2m+1$, do $2^m\equiv\pm1\pmod n$ and $2^m\equiv2\pmod m$ imply $n$ prime? Note: equivalence follows ...
Suppose $M_m = 2^m - 1$ is a number that is known to be composite, and $m$ is prime. However, how do I show that it satisfy the property of $2^{M_m} \equiv 2 \pmod {M_m}$ such that it is a pseudo-...
For a prime number $p$, and an $a$ such that $\ \ 1<a<p-1$, we have: $\ \ \ a^{p-1} \equiv 1\ \pmod p$ To test the primality of a number, this is applied multiple times for randomly ...