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
73 views

76 views

Show that $1373653$ is a strong pseudoprime to base $3$

How can I show that $n = 1373653$ is a strong pseudoprime to base $3$? I found this question as an exercise in a book I'm currently reading (which unfortunately doesnt provide a solution to this ...
23 views

Relations between Pseudoprimes

good to everyone. I need your help. Does anyone know the relationships between the pseudoprimes ​​of Catalan, Euler-Jacobi, Frobenius, Lucas, Somer-Lucas and Perrin? and with other pseudoprimes? A ...
153 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 ...
195 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 ...
26 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$  If $(x+b)^n = -x+b \mod (n,x^2-a)$, then $n$...
75 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$...
74 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 ...
122 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 (...
55 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 ...
43 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 ...
58 views

90 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 ...
46 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, ...
44 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 ...
33 views

113 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 ...
41 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 ...
75 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\}$. ...
66 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\}$ ...
21 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.
38 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.
95 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 ...
98 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-...
37 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 ...
122 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 ...
44 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$$ ...
47 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....
53 views

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