Questions tagged [prime-numbers]
Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.
8,636 questions
0
votes
1answer
23 views
Should you use Euler's generalization of fermat's little theorem for primality testing?
The title is a bit long, but i think it explains my question well.
Let's say we want to test if an integer p is prime
With Fermat's Little Theorem this is a simple check if
$a^{p-1} \equiv 1 (mod \ ...
1
vote
0answers
17 views
A funny inequality problem of Logarithmic integral function and prime number
Let
$E(x)=\left(5.5 \times 10^{9}+2.3 \times 10^{-8} \operatorname{li}(x)+10^{-11} x\right) \log x$,
$E_{1}(x)=\left(5.5 \times 10^{9}+2.3 \times 10^{-8} \operatorname{li}(x)\right) \log x$,
$\...
4
votes
0answers
26 views
Pairs of palindromic primes without $1$ and have a palindromic product
While discussing about prime numbers with other users, I noticed that:
$(1)$ There are very few pairs of palindromic prime numbers that have products which are palindromes.
Ex : $[2, 3], [2, 30203],...
2
votes
0answers
23 views
Reasoning about remainders and the Möbius function
This one seems counter intuitive to me but I am not seeing a mistake in my reasoning.
Please let me know if you find one.
Let:
$x > 0$ be an integer
$\mu(x)$ be the möbius function
$x\#$ be the ...
1
vote
1answer
56 views
Find the smallest $n$ such that the $n$-th prime $p_n \equiv 330 \mod n $.
Find the smallest $n > 1$ such that the $n$-th prime $p_n \equiv 330 \mod n $.
I was investigating the remainders when the $n$-th prime is divided by $n$. For every positive integer $a < 330$, ...
0
votes
3answers
45 views
Find all primes $p$ for which $19 p - 1$ is a perfect cube
I set the equation to $19 p - 1 = n^3$, then got $19 p =(n+1)(n^2-n+1)$. I don't know what to do now.
-2
votes
0answers
46 views
Relationship between $n$ and $P_{n}$
We often hear it said that either there is no relation between the natural, or counting numbers, $n$, and their counterparts the primes, $P_{n}$, or that if there is, it is so recondite as to be ...
0
votes
0answers
39 views
Computing Integers' Prime Factorization Using the General Number Field Sieve
Recently, I have taken upon myself the task of writing an algorithm to compute the prime factorization of an integer. I am neither a mathematician nor a programmer/computers' engineer as an occupation,...
4
votes
0answers
58 views
Are 2, 3 the only prime numbers that don't have the digit 1 and are palindromes whose squares are also palindromes?
While thinking about prime numbers, I noticed that:
$(1)$ Very few prime numbers have squares that are palindromes.
Ex: $2$, $3$, $11$, $101$, $307$
$(2)$ Even rarer are prime numbers that are ...
3
votes
2answers
76 views
Distribution of prime numbers modulo $4$
Are primes equally likely to be equivalent to $1$ or $3$ modulo $4,$ or is there a skew in one direction?
That is my specific question, but I would be interested to know if there exists a trend more ...
2
votes
0answers
53 views
Primality test for numbers of the form $N=k \cdot 3^n-1$
Can you provide proof or counterexample for the claim given below?
Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following claim:
Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(...
8
votes
0answers
53 views
Are there infinitely many solutions such that the digit sum of a prime power is a smaller power of the same prime?
While discussing prime powers and divisors, I came up with the following problem.
Examples
$\to$ prime $p=3$
digit sum (in base ten) of $p^3=27$ is $p^2=9$, a power of $p$,.
$\to$ prime $p=7$
...
3
votes
2answers
58 views
Given $p_1^{a_1}+ \dots + p_r^{a_r} \leq n$, show that : $r \leq 2\sqrt{\frac{n}{\log(n)}}(1+o(1))$
I post here because I really don't succeed to prove this :
Given $p_1^{a_1}+ \dots + p_r^{a_r} \leq n$, $p_i$ distinct prime numbers and $a_i \in \mathbb{N} $, $a_i \geq 1$, $r \in \mathbb{N} $, ...
1
vote
0answers
47 views
Does this explicit formula for the prime-counting function $\pi(x)$ converge?
This question is related to an answer I posted earlier at the following link.
Explicit Formula for $\pi(x)$
A potential explicit formula for the fundamental prime-counting function $\pi(x)$ is ...
4
votes
0answers
81 views
Is there another pair of consecutive primes with this property?
Denote $$r(n)$$ to be the number that occurs if we reverse the digits of $n$
Suppose, $\ (p,q)\ $ is a pair of consecutive primes.
The only prime $p$ with the property $$r(p)=2q$$ I found is $\ p=...
2
votes
1answer
44 views
Counting integers with a least prime factor greater than $x$ in a sequence of $x$ consecutive integers.
It is well known from Sylvester-Schur that in any sequence of $x$ consecutive integers, there is always at least one integer divisible by a prime greater than $x$.
I am interested in counting the ...
4
votes
0answers
41 views
Why are some Ramanujan $G_n$ and $g_n$ functions highly factorable?
Given the Dedekind eta function $\eta(\tau)$ with $\tau = \sqrt{-n}$. Define the Ramanujan $G_n$ and $g_n$ functions as,
$$G_n = 2^{-1/4}\frac{\eta^2(\tau)}{\eta(\tau/2)\,\eta(2\tau)}$$
$$g_n = 2^{-1/...
1
vote
0answers
53 views
When is $a(n)$ prime?
Question: When is $a(n)\in P$ compared to all possible values of $n$? where $P$ denotes the set of primes. What is the density of the primes in the sequence?
Consider the sum of the prime counting ...
1
vote
1answer
55 views
Prime numbers & perfect squares
Find all prime numbers such that $2p^4-p^2+16$ is a perfect square.
$2p^4-p^2+16=n^2$
$16-n^2=p^2-2p^4$
$(4-n)(4+n)=p^2(1-2p^2)$
What should I do next?
0
votes
1answer
48 views
Find all prime numbers $p$ such that $5^p+ 4p^4$ is a perfect square
Find all prime numbers $p$ such that $5^p+ 4p^4$ is a perfect square.
I cannot find a single solution to this problem that has $p$ as a prime number.
2
votes
2answers
69 views
Counting the number of integers with their least prime factor greater than $x$ between $ax$ and $ax+x$
Let:
$x \ge 2, a \ge 1$ be integers.
$x\#$ be the primorial for $x$
$\mu(i)$ be the möbius function.
$\text{lpf}(x)$ be the least prime factor of $x$.
$p_k$ be the $k$th prime which is the highest ...
4
votes
1answer
63 views
How to estimate $\sum_{p\leqslant x}\sum_{q\leqslant x}\frac{1}{p+q}$?
How to estimate $$\sum_{p\leqslant x}\sum_{q\leqslant x}\frac{1}{p+q}, \qquad\qquad(1)$$
where $p$, $q$ are prime numbers.
We have the Mertens' formula
$$ \sum_{p\leqslant x} \frac{1}{p} = \log\log ...
1
vote
1answer
21 views
For two different products of primes with rational powers, are the real number representations always unique?
So from the fundamental theorem of arithmetic we have that every $\prod_{i=0}^{n}p_{i}^{e_{i}}$, for some $ e_i \hspace{2px} \epsilon \hspace{2px} \mathbb{N} $ and prime numbers $p_i$, gives a unique ...
1
vote
0answers
45 views
Lipschitz primes
A Lipschitz integer is a Quaternion with integer coefficients. The norm is defined as $N(a+ib+jc+kd)=a^2+b^2+c^2+d^2$ which is a multiplicative function
$N:\mathbb H\to\mathbb R$, $N(\alpha\beta)=N(\...
1
vote
2answers
47 views
Using Dirichlet's theorem to show existence of number coprime to $n$
I have the following question: Let $n$ be a positive integer and $d$ be divisor of $n$. Use Dirichlet's theorem to show that there exists an integer $k$, where $1\le k\le d-1$ such that the number $m:=...
2
votes
2answers
68 views
Find all primes that satisfy the congruency $100^p \equiv 1 \mod p$
Find all primes that satisfy congruency $100^p\equiv1\mod p$
I've tried reducing it to the fact that $100^p=(10^p)^2$ so then $10^p \equiv 1 \mod p$ or $-1 \mod p$.
I've also attempted writing this ...
0
votes
1answer
28 views
In what bases is $101$ the only prime in the sequence $1,101,10101,\ldots$?
$101$ is the only prime in the sequence $1,101,10101,\ldots$ as shown in this Putnam question.
I also know from studying the Collatz conjecture that $101_2$ is also the only prime in the same ...
1
vote
1answer
74 views
Does digit $6$ always lead to $\ 25921=161^2\ $?
Consider prime numbers with the property that the product of the factorials of the digits plus $1$ is a perfect square, for example the prime $$30241$$ leads to the square $$3!\cdot 0!\cdot 2!\cdot 4!\...
0
votes
1answer
13 views
What is the sum of the following series with a prime denominator
$$\sum_{j=1}^{546}\left[ \frac{(5j)}{(1093)}\right ]$$
Where the brackets are the floor function. I'm not even sure how to start this question besides just figuring out for how many numbers the floor ...
0
votes
1answer
45 views
Easy proof of falsehood of $\pi(n) \leq C \cdot \text{ln}(n)$ for the prime counting function $\pi$
Let $\pi(n)$ be the number of primes in the range $1,\dotsc,n$.
The following statement is true: There is no $C>0$ such that $\pi(n) \leq C \cdot \text{ln}(n)$ for all $n\geq 1$.
It follows ...
2
votes
2answers
58 views
Reasoning about $\left(\left\lfloor\frac{2x}{i}\right\rfloor -2\left\lfloor\frac{x}{i}\right\rfloor\right)$
I am working on an alternative argument for Bertrand's Postulate that depends on the following argument.
Please let me know if I made a mistake or if any point is unclear.
Let:
$p_k$ be the $k$th ...
4
votes
3answers
110 views
prime numbers and expressing non-prime numbers
My textbook says if $b$ is a non-prime number then it can be expressed as a product of prime numbers. But if $1$ isn't prime how it can be expressed as a product of prime numbers?
0
votes
0answers
26 views
Citizens and rebels: a twin prime related categorization of composites
Assuming Goldbach's conjecture and denoting by $r_{0}(n)$ the quantity $\inf\{r>0,(n-r,n+r)\in\mathbb{P}^{2}\}$ for a large enough composite integer $n$, consider the sequence $(u_n)_n$ such that $...
2
votes
2answers
60 views
What is the probability that $\exists N \in \mathbb{N}$ such that $\forall n > N$, $2n \in C + C$?
Suppose $C$ is a random subset of $\mathbb{N}\setminus\{1, 2\}$, such that $\forall n \in \mathbb{N}\setminus\{1, 2\}$, $P(n \in C) = \frac{1}{\ln(n)}$ and the events of different numbers belonging to ...
1
vote
1answer
18 views
Bound of logarithmic integral function
Does logarithmic integral function bound from above the prime-counting function? In other words, does it hold that $\pi(x) \le li(x)$ or even $\pi(x)\le Li(x)$?
-1
votes
0answers
51 views
Efficient primorial modulo [closed]
The product of the first $n$ primes is called the $n$-th primorial: $$p_n \# = \prod_{k=1}^n p_n.$$
Is there a shortcut for calculating $x ≡ p_n \mod p_{n+1}$?
7
votes
2answers
112 views
Show that $(\binom{p^2}{p} -p ) $ is divisible by $p^5$, for every prime number $p, p\ge 5$
Show that $(\binom{p^2}{p} -p ) $ is divisible by $p^5$, for every prime number $p, p\ge 5$.
I have a combinatorics problem, and this is what it reduces to. I am not quite sure how to link the fifth ...
-1
votes
1answer
39 views
Can $(2n-1)^2+2(2n-1)k$ generate primes for $n>1$?
I have a function $$A=(2n-1)^2+2(2n-1)k$$ that I have proven, to myself, to generate $all$ values of $A$ for Pythagorean triples where GCD(A,B,C) is an odd square – so it includes all primitives. Let'...
1
vote
0answers
44 views
How could factordb apply the p-1-method on this number?
The following partial factorization
http://factordb.com/index.php?id=1100000001285565404
was used by factordb to prove this number ($\ 32^{2133}+4^{2133}+1\ $) to be prime.
http://factordb.com/...
6
votes
1answer
81 views
+50
Topological Algebraic Independence of power series
Let $p$ be a prime number, let $x$ be a variable, and consider two power series over the ring $\mathbb{Z}_p$ of $p$-adic integers:
$a(x):=\underset{n\geq 1}{\sum}{\frac{p^n}{n!}x^n}=px+\frac{p^2}{2}x^...
0
votes
1answer
28 views
Last three numbers of multiple of four primes
If we have four two-digit prime numbers $p_1$, $p_2$, $p_3$ and $p_ 4$ such that they all end with a different number. For example 11, 13, 17 and 19. What can be the last three digits of $...
1
vote
1answer
138 views
Can the solution to $n^2=pq+y^2$ help with the Golbach conjecture?
This question was inspired by the following question.
https://mathoverflow.net/questions/132532/goldbachs-conjecture-and-eulers-idoneal-numbers
Here, we are not looking to factor an integer $N$. ...
3
votes
1answer
182 views
Show that $n = 3^{100} + 2$ is not a prime number.
So I have to prove that $n = 3^{100} + 2$ is not a prime number while we assume that $X^2 - 53$ has no zeroes in $\mathbb{Z}/n\mathbb{Z}$.
Because we are working with quadratic reciprocity in this ...
2
votes
0answers
42 views
Is $\zeta(s)\sim\sqrt{\frac{\zeta(4s)}{\zeta(2s)}}\prod\limits_{n=1}^\infty\big(1-\frac{2}{p_n^s+p_n^{-s}}\big)^{-1/2}$?
The Riemann Zeta function, denoted by $\zeta(\cdot)$, is defined by the following equation for $s > 1$ and $p_n$ the $n^\text{th}$ prime number. $$\zeta(s)=\prod_{n=1}^\infty\bigg(1-\frac{1}{p_n^s}\...
1
vote
1answer
76 views
Would this function work as a test for prime?
Would the function
$$\sum_{a=2}^\infty H\!\left(x-a\sum_{n=0}^\infty H(x-na)\right)$$
(H(x) is the Heaviside step function)
Work as a test for prime numbers
it is zero when x is prime
And a ...
1
vote
2answers
56 views
Show that there is always one integer $t$ with a least prime factor $> 5$ where $x < t \le x+6$
Let $p_k$ be the $k$th prime.
Let $f_2(x) = \lfloor x\rfloor - \left\lfloor\dfrac{x}{2}\right\rfloor$
For $k > 1$, let:
$f_{p_k}(x) = f_{p_{k-1}}(\lfloor x\rfloor) - f_{p_{k-1}}\left(\left\...
-1
votes
2answers
45 views
How do I solve the for the base of an exponential modular arithmetic equation? [closed]
The question is:
$$10 \equiv M^5 \mod{35}$$
How do I isolate and solve for $M$?
2
votes
1answer
56 views
Primality test for Mersenne numbers using the fourth Chebyshev polynomial of the first kind
Can you provide a proof or a counterexample for the claim given below?
Inspired by Lucas-Lehmer test I have formulated the following claim :
Let $T_n(x)$ be the nth Chebyshev polynomial of the ...
1
vote
1answer
50 views
Little question about gcd and Fermat pseudoprimes.
From Wikipedia:
...a Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation:
$1)$ $b^{n-1}\equiv 1{\pmod {n}}$
for all integers $b$ which ...
0
votes
0answers
117 views
Are prime numbers classified by level rarefying among primes?
Conjecture: The prime numbers classified by level are rarefying among primes.
Edit after Ricardo comment: I use rarefy like in "Théorème de la raréfaction des nombres premiers" but maybe it's not ...
