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.

2
votes
1answer
78 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
18 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
27 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
105 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
28 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
59 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
41 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
28 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
19 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
36 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
82 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
88 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
30 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
91 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
32 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
40 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
46 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
0answers
30 views

If $x=2^m$ and $y=10^n$ , is $703$ the only fermat-pseudoprime of the form $2xy+x-y-1$ to base $3$?

Suppose, $m$ and $n$ are positive integers and $x=2^m$ and $y=10^n$ When can $$2xy+x-y-1$$ be a (weak) Fermat-pseudoprime to base $3$ ? The only pair I found so far is $m=n=2$ giving $703=19\cdot ...
1
vote
1answer
198 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
69 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
60 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
152 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
21 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
77 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
77 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
39 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
39 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
300 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
77 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
572 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 ...
0
votes
1answer
255 views

561 Euler pseudoprime bases

I am asked to find all bases for which 561 is an Euler pseudoprime. Unfortunately, the lecturer did not tell us how to do this in a systematic way. Any help?
1
vote
1answer
61 views

Has anyone explored prime-like numbers in other dimensions?

Prime numbers are often described with an example like the following: 'if you have n counters, and can't make a rectangle which has both sides longer than 1, n is prime' I think it would be ...
1
vote
0answers
54 views

Useful sufficient condition for a fermat-pseudoprime to base $2$?

Suppose $p<q$ are odd prime numbers. I only know the following easy to verify sufficient condition that $N=pq$ is a fermat-pseudoprime to base $2$, in other words that $$2^{N-1}\equiv 1\mod N$$ ...
2
votes
0answers
132 views

How reliable is the weak Fermat-test for base $2$ for large numbers , for example $100$-digit-numbers?

Let $N$ be a $100$-digit odd random number. Suppose , $$2^{N-1}\equiv 1\mod N$$ How large is approximately the probability that $N$ is composite ? In other words : How reliable is the weak-fermat-...
1
vote
2answers
488 views

Show 1387 is a base 2 pseudoprime and is also composite using Miller's test

My attempt: 1387 is a base 2 pseudoprime if $2^{1386} \equiv 1 \bmod 1387$. We note $1387=19 \cdot 73$ and $1386=18 \cdot 7 \cdot 11$, and by Fermat's Little Theorem(FLT), $2^{18} \equiv 1 \bmod 19$, ...
1
vote
4answers
478 views

Why is this deterministic variant of Miller-Rabin not working?

I am using this paper as a reference. The Miller-Rabin test, as classically formulated, is non-deterministic -- you pick a base $b$, check if your number $n$ is a $b$-strong probable prime ($b$-SPRP),...
1
vote
0answers
32 views

What is the probability $p_k$ that a random $k$-digit $2$-sprp is composite?

Let $k$ be a positive integer and $N$ a random $k$-digit number. Suppose $N$ is strong probable prime to base $2$. What is the probability $p_k$ that $N$ is composite ? There are infinite many ...
5
votes
1answer
232 views

What is the fastest way to get the next Carmichael-number?

A Carmichael number is a composite number $N$, such that $a^{N-1}\equiv 1\mod N$ holds for every $a$ coprime to $N$. $N$ is a Carmichael number if $N$ is odd and squarefree $N$ has at least three ...
3
votes
0answers
52 views

How large will the smallest counterexample to the BPSW-test be?

Here: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test an effective prime-test is mentioned that apparently does not have a small counterexample. Here : http://mathworld.wolfram....
1
vote
0answers
19 views

Can we estimate the number of composite strong-probable primes to base $2$ in some interval?

Suppose, an interval $[a,b]$ with positive integers $a<b$ is given. Can we estimate the number of composite strong-probable primes to base $2$ in [a,b] ? In particular, I am interested in ...
4
votes
1answer
66 views

Is the occurence of $4653$ in both expressions a coincidence?

The smallest composite strong-probable prime to base $2$ greater than $10^5$ is $$10^5+4653$$ and the smallest composite strong-probable prime to base $2$ greater than $10^6$ is $$10^6+4653$$ Is it ...
3
votes
1answer
83 views

Are there further “sandwich”-Carmichael-numbers?

A Carmichael number $N$ has the property that for every $a$ coprime to $N$, the equation $a^{N-1}\equiv 1\mod N$ holds, although $N$ is composite. A number $N$ is a Carmichael number, if $N$ is odd ...
4
votes
1answer
132 views

Fermat and strong pseudoprimes

A composite number is said to be a Fermat pseudoprime to the base $a$ if $\gcd(a, n) = 1$ and $a^{n - 1} \equiv 1 \bmod n$. Let $n$ be an odd composite number, $n = t2^k + 1$ with $t$ odd. Let $a$ be ...
1
vote
1answer
132 views

Fermat pseudoprime

Let $n=pq$ product of two different primes. Let $d=\gcd(p-1,q-1)$. Prove that $n$ is a Fermat pseudoprime to the base $a$ if and only if $a^d=1 \mod n$ I believe that I get: if $a^d=1 \mod n$ then $n$...
6
votes
2answers
169 views

What type of pseudoprime does the largest known pseudoprime tend to be?

It is a well-known fact that the largest known prime number for several decades now has been a Mersenne prime, even though more and more of them have been found over the years and there have also been ...
4
votes
1answer
204 views

What is the connection between Fermat's Little Theorem and “Fermat Liars”?

I know that Fermat's Little Theorem states that if $p$ is prime and $1 < a < p$, then $a^{p-1} \equiv 1 ($mod $p)$. I also know that a Fermat Liar is any $a$ such that $a^{n-1} \equiv 1 ($mod $...
3
votes
3answers
347 views

Showing numbers are Carmichael Numbers

I'm currently working through a problem set for mathematical cryptography and came across a question which asks: Say why $ 676, 75, 143 $ are not Carmichael Numbers Furthermore, explain why ...
5
votes
1answer
114 views

Fermat's test to prove pseudoprimes

I'm self teaching myself number theory as I'm doing a course in cryptography and anything I've found hasn't helped. The question I'm stuck on is: Use Fermat Test to show 19 is a pseudoprime base 3 ...
1
vote
1answer
1k views

Show that every composite Fermat number is a pseudoprime base 2.

Question: Show that every composite Fermat number $F_m=2^{2^m}+1$ is a pseudoprime base 2. Hint: Raise the congruence $2^{2^m}\equiv-1($mod $F_m)$ to the $2^{2^m-m}$th power. Even with the hint, I'm ...
0
votes
4answers
129 views

Why is $561$ missing from this list?

On the MathWorld page: http://mathworld.wolfram.com/FermatPseudoprime.html in the first table, I expect to see $561$ on every line, but it is not on the line for base $3$. When you click on the ...