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.

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
-2
votes
2answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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$...
2
votes
1answer
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$...
0
votes
1answer
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 ...
1
vote
2answers
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 (...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
3
votes
2answers
45 views

Show that, for each $n \geq 2$, the whole number $4n^{2}-1$ is a Fermat pseudoprime to base $2n$

I need to show that, for each $n \geq 2$, the whole number $4n^{2}-1$ is a Fermat pseudoprime to base $2n$; (hint: $4n^{2}-2$ is a multiple of $2$). Fermat pseudoprime to base $2n$ means that $(2n)^{...
3
votes
1answer
121 views

Is there an infinite Carmichael numbers of this form $K.p^n+1$

Carmichael numbers are these numbers that passes fermat test for any base from $1$ to $N-1$ EX : $a^{561} \equiv a \pmod {561} $ where $ 1 \le a \le 560 $ These numbers are infinite, and I have ...
1
vote
1answer
35 views

Miller's Test Base a [closed]

Definition - Miller's test base a- For the following example, please advise on why Miller's test passes according to the output. Thank you!
4
votes
2answers
142 views

Why am I getting the wrong result when applying the extra strong Lucas pseudoprime test?

I'm trying to do the Lucas extra strong pseudoprime test but get the wrong result. For example $13$ is prime but the test gives composite. Here is what I tried: $n=13$ then $n+1=14=7 \cdot 2^1$ gives ...
8
votes
0answers
99 views

Are there any $3$-Fermat-pseudoprimes of the form $k^4+1$?

Suppose , $k$ is a positive integer and $N:=k^4+1$ composite. Can $N$ be a $3$-Fermat-pseudoprime, that is can the congruence $$3^{N-1}\equiv 1\mod N$$ hold ? I verified upto $k=10^8$ and found no ...
7
votes
1answer
87 views

What is the ratio of Carmichael pseduo-primes to true primes for $1$ to $n$? Or is it known?

Let $\pi(n)$ be the prime counting function. And let $\varphi(n)$ be the count of Carmichael pseudo-primes for $1$ to $n$. Is the ratio, $$\frac{\varphi(n)}{\pi(n)}$$ is known, as $n \to \infty$? I ...
4
votes
0answers
56 views

Does There Exist a Lucas Sequences with No Pseudoprimes?

I would like to ask a general question that conversely is related to the subject of the post: Fibonacci pseudoprimes Has any non-trivial Lucas (or extended Lucas (i.e. Lehmer)) sequence been found ...
2
votes
3answers
67 views

Prove that $p$ is Composite by Showing that It is Not a Pseudoprime Basis $2$

I have the following problem: Prove that $m \notin \mathbb{P} $ by showing that m is not a pseudoprime to the basis $2$. I think normally the problem is not that difficult, but in this case $m= ...
0
votes
1answer
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 ...
1
vote
1answer
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, ...
0
votes
1answer
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 ...
0
votes
1answer
28 views

Finding the mistake in a proof of pseudo-primality

I am trying to find the mistake in the following "proof", which shows that a Fermat-pseudoprime $n$ with respect to $a$ is also a strong pseudoprime with respect to $a$. "Write $n-1=2^st$ with $t\in\...
2
votes
1answer
106 views

$\frac{4^p - 1}{3}$ is a Fermat pseudoprime with respect to 2

I have to prove that $n = \frac{4^p - 1}{3}$ is a Fermat pseudoprime with respect to $2$ when $p \geq 5$ is a prime number. I have proved that $n$ is not prime because $4^p - 1 = (2^p-1)(2^p+1)$ and $(...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
3answers
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\}$. ...
3
votes
0answers
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. ...
2
votes
0answers
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\}$ ...
1
vote
0answers
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.
1
vote
0answers
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.
3
votes
0answers
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 ...
1
vote
1answer
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-...
0
votes
0answers
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 ...
6
votes
0answers
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 ...
2
votes
0answers
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$$ ...
3
votes
0answers
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....
1
vote
0answers
50 views

Is this proof for pseudo primes suitable?

Given that $$ab\equiv 1 \pmod n$$ and $n$ is a pseudo prime base $a$, Show that $b$ is also a base for pseudo prime n. I can raise to the power of $n$: $$(ab)^{n}\equiv 1 \pmod n$$ $$a^{n}{b}^{n}\...
0
votes
1answer
434 views

What's the difference between a Fermat pseudoprime and a Carmichael number?

I've read a lot of definitions in different places on the Internet and I'm confused since all of them express the same thing, but using seemingly different explanations. Can somebody please point out ...
2
votes
0answers
88 views

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

How can I show that $3281$ is a strong pseudoprime to base $3$? My attempt: $3^d≡1$ mod $3281$, which is true for $d=16k$ and $3281=17\cdot193$. Hence $3281$ is a strong pseudoprime to base $3$. ...
2
votes
0answers
87 views

Passing k rounds of the Miller Rabin probabilistic test

I am having trouble understanding why the following statement holds: Consider a procedure which chooses a random odd number $n\leq x$ and then performs $k$ independent strong prime test on $n$ with ...
1
vote
1answer
249 views

Lucas Sequence and primality tests. is this test deterministic?

consider lucas parameters $(P, Q)$ and $D = P^2 - 4Q$. Let $n>0$,$\big(\frac{D}{n}\big)= - 1$ then $U_{n + 1}\equiv{0 \pmod{n}}$ and $n$ is a Lucas probable prime. This test base only on the ...
2
votes
0answers
27 views

If n = $\frac{a^{2p}-1}{a^2-1}$ where $a$ is an integer $>1$ and $p$ is an odd prime, then $n$ is pseudoprime to the base $a$. [duplicate]

Show that if $n = \frac{a^{2p}-1}{a^2-1}$ where $a$ is an integer $>1$ and $p$ is an oddprime that doesn't divide $a(a^2-1)$, then $n$ is pseudoprime to the base $a$. Conclude that there are ...
2
votes
0answers
117 views

Is this the best primality test using second order recurrences (Lucas Sequences)?

little Explanation Using second order lucas sequences $$U_{n + 2} = P\cdot{U_{n -1}} - Q\cdot{U_{n}}\qquad U_0=0, U_1=1$$ $$V_{n + 2} = P\cdot{V_{n -1}} - Q\cdot{V_{n}},\qquad V_0=2, V_1=P$$ Now our ...
1
vote
1answer
167 views

Show that all Fermat numbers pass the base $2$ test (pseudoprime).

I realize that there is a similar post to this, but that post included a hint which we were not given. Also regarding that hint, I'm just wondering how someone could find it out for themselves. Here ...
1
vote
1answer
44 views

Could be Euler product for Riemann zeta function runs over pseudo-prime?

The Euler product over primes defined as :$$\zeta(s)=\prod_{p \ \text{prime}} \frac{1}{1-p^{-s}}\tag{01}$$ , My question Here is : is it possible to write this product $(01)$ for which run or ...
1
vote
1answer
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 ...
6
votes
1answer
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 ...
2
votes
1answer
103 views

How do I show that this number is a pseudo prime?

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-...
2
votes
1answer
802 views

How many times should Fermat's primality test be applied?

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