Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

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