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.

1,833 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
142 views

Polynomial detecting congruence conditions

It is well-known that a prime number $p$ is $\equiv 1 \pmod 4$ iff $p=x^2+y^2$ for some integers $x,y$ (except for $p=2$). My question is: is there an irreducible homogeneous polynomial $f \in \Bbb Z[...
9
votes
0answers
117 views

Can a prime have arbitary many representations as a sum of two perfect powers?

Let $p$ be a prime number and $f(p)$ be the number of representations $$p=a+b$$ with perfect powers $0<a< b$ For example, $13$ has the only representation $$4+9=13$$ hence $f(13)=1$ $$41=9+32=...
9
votes
1answer
208 views

On integer values which are attained by $n/\pi(n)$ only once

Let $\pi (n)$ denote the prime counting function. I can prove that $\mathbb N \setminus \{1\} \subseteq \{n/ \pi(n) : n \in \mathbb N \}$ . Now for every integer $m>1$ , define $s(m) := \{ n \in \...
9
votes
0answers
162 views

Infinitely many primes divide some $\sum_{k=1}^n k!$

For a positive integer $n$ define $$a_n=\sum_{k=1}^n k!.$$ Prove that the set of primes that divide some $a_n$ is infinite. Some progress I guess. Let $S$ be the set of primes dividing some $a_n$, ...
9
votes
1answer
427 views

Generalisation of prime numbers to matrices?

Is it possible to generalise prime numbers to matrices? I'm trying to solve a Rubix cube in the minimum number of steps and I think this would be useful. I think it's possible to represent Rubix cube ...
9
votes
0answers
462 views

An interesting problem which only needs elementary number theory

A problem about elementary number theory While writing my paper, I came across the following problem: (all the discussion assume that $q$ is prime and $\alpha $ is a positive integer. ) We first ...
9
votes
0answers
292 views

Number of primitive roots mod $p$ that are not primitive roots mod $p^2$

Consider the primitive roots of a prime $p$ in the range $1...p$ which are not primitive roots mod $p^2$. Let $n(p)$ be this number. While looking for an answer to this question, it seems that the ...
9
votes
1answer
118 views

Prime Concatenation Order

Consider the following procedure. Given an integer $n \geq 2$, obtain the canonical prime factorization of $n$, i.e. $\prod_{i=1}^k p_i^{e_i}$. Take the distinct factors $p_i$ and list them in ...
9
votes
0answers
423 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
9
votes
0answers
203 views

Primality of $n! +1$

I came across with a problem where I was required to examine primality of $n! +1$ (17! + 1 was the actual number). Although Wilson's Theorem could be manipulated for determining primality of $n! + 1$...
9
votes
1answer
179 views

$pq\equiv 1\pmod 4$, how to find $p,q\bmod 4$?

Somebody asked me a question, I have no idea about it, the question is: If a positive integer $n\equiv 1\pmod 4$ is the product of two primes, (denotes $n=pq,$ such as a RSA number) but we don't ...
9
votes
1answer
249 views

How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?

Is there an easy way to compute the following question: How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes? The only thing that ...
8
votes
0answers
67 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$ ...
8
votes
0answers
165 views

Is $\small \sum\limits_{p\leq x}\pi\left(\frac{x^2}{p}\right)-\sum\limits_{p\gt x}\pi\left(\frac{x^2}{p}\right)=\pi^2(x)$ of any use?

I was playing with some Meissel/Lehmer formulas and I found this one. In fact there is a much simpler way to find it when looking closer, so I guess i is well known. $$\sum\limits_{p\leq x}\pi\left(\...
8
votes
0answers
127 views

Odd numbers with $\varphi(n)/n < 1/2$

The topic was also discussed in this MathOverflow question. From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ ...
8
votes
1answer
239 views

Do further prime numbers of the form $n^n+\varphi(n)$ exist?

Can the expression $$n^n+\varphi(n)$$ be a prime number for some integer $n>19$ ? For $n=1,2,3,19$ and no other positive integer $n\le 3\ 000$, the expression is prime. A further prime of the ...
8
votes
0answers
281 views

Interesting sequence involving prime numbers jumping on the number line.

Udpate 4: Trying to characterize finite and infinite cycles. Update 3: All primes $a_0\ge29$ seem to either have infinite cycles or finite non-terminating cycles that converge to infinite cycles of ...
8
votes
0answers
144 views

Solving $x^2+x+1=7^n$

Do simple equations $x^2+x+1=7^n$ have infinitely or finitely many solutions? In fact, what about the general equation $x^2+x+1=p^n$ where $p$ is a prime congruent to $1$ $\pmod 3$? Are there any ...
8
votes
0answers
148 views

The practical usage of Arnold Matrix Trace Theorem

I would like to ask about the Arnold's Matrix Trace theorem: $$\textrm{tr}\big(A^{p^k}\big)\equiv\textrm{tr}\big(A^{p^{k-1}}\big)\ (\!\!\bmod {p^k}).$$ This theorem looks fantastic to me. But is ...
8
votes
0answers
103 views

About the regularity of the decomposition in prime factors

Definition of $\rho$. Let's consider a function $\rho$, acting on the prime decomposition of an integer $n$: $$\begin{matrix} \rho\colon & \mathbb N_{\geqslant 1}&\to &\mathbb N_{\...
8
votes
0answers
154 views

There at least 4 divisors of $n-1$ which do not divide $\phi(n)$ if $n$ is a composite of the form $6k+1$.

I observed that if $n$ is a composite number of the form $6k + 1$ then there are at least three divisors of $n - 1$ which do not divide $\phi(n)$ (Euler's totient function). Is this true in general? ...
8
votes
0answers
219 views

The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
8
votes
0answers
124 views

Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
8
votes
0answers
88 views

To what extent can the fondamental theorem of arithmetic be used to give a canonical form to non-integer numbers?

The fundamental theorem of arithmetic gives us a unique way of writing any non-zero integer. For any $n \in \mathbb{Z}^*$, we have a unique decomposition : $$n = (-1)^\epsilon \prod\limits_{i \in \...
8
votes
1answer
184 views

Goldbach for certain classes of $n$

The Wiki article on the Goldbach conjecture (where $\#$ of ways even $n$ can be represented by prime additions is heareafter denoted $G(n)$) states that In 1975, Hugh Montgomery and Robert Charles ...
8
votes
0answers
519 views

Prime spiral with regular triangles

I wrote a little program that creates a Ulam like spiral, only with regular triangles instead of squares. The following image shows the way it is set up: In this set up all the uneven numbers will be ...
8
votes
0answers
355 views

Basic Olympiad number theory problem about prime numbers

I'm learning a basic lesson of number theory and get stuck with this : Find all positive integers $n$ and prime numbers $p$ such that $n^p+3^p$ is a perfect square. I found that if $p \ge 3$, then $...
8
votes
0answers
453 views

Primes $p$ for which $2p \pm 1$ are also primes

Out of curiosity and trouble sleeping, I decided to look at the distribution of primes $p$ for which $2p \pm 1$ are also primes. I looked at the first 25,910,000 primes and counted the number of ...
8
votes
0answers
277 views

Relatives of Heegner numbers?

It is well known that Euler's lucky numbers are related to the Heegner numbers, where \begin{align} &n^2+n+p\\ \end{align} gives primes for $n=0,\dots,p-2$ if and only if its discriminant $1-4p$...
8
votes
0answers
300 views

The effect of roots of Dirichlet's $\beta$ function condenses to $\frac12\left(1+ie^{i2\pi\frac{p}4}\right)$

With the help of Raymond Manzoni and Greg Martin I was able to derive an explicit formula for the number of primes of the form $4n+3$ in terms of (sums of) sums of Riemann's $R$ functions over roots ...
8
votes
0answers
248 views

Prime numbers, analysis of polylogarithms

Can any interesting results concering prime numbers be obtained using the analytic properties of the polylogarithm, similar to how analytic methods are used on the zeta function to obtain results ...
8
votes
1answer
180 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 do not contain the digit $1$ and that have products which are ...
7
votes
1answer
127 views

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^...
7
votes
0answers
133 views

Is there a simple formula for $\binom{2n}{n} \pmod{n^3}$?

Is there a simple formula for the following? $$f(n) = \binom{2n}{n} \pmod{n^3}$$ I know $f(n) = 2$ iff $n$ is prime and greater than $3$, but I don't know anything about composite numbers.
7
votes
0answers
146 views

What is the relationship between simple prime-power counting function and $\log\zeta(s)$?

This question assumes the following definitions of prime-counting functions where $p$ denotes a prime number, $k$ denotes a positive integer, and $\theta(y)$ is the Heaviside step function which takes ...
7
votes
0answers
524 views

Is there a number of the form $f(n)=7k+6=5p$ with prime $p$?

Here : Numbers $n$ of the form $10^{m}(2^{k}−1)+2^{k-1}−1$, where $m$ is the number of decimal digits of $ 2^{k-1}$. the numbers $$f(n):=(2^n-1)\cdot 10^d+2^{n-1}-1$$ are introduced , where $d$ ...
7
votes
2answers
309 views

Why the infinity of prime numbers can be proved topologically?

I was reading Proofs from THE BOOK by Martin Aigner, Günter M. Ziegler and was very impressed by the following proof of infinity of prime numbers with topology: Edit: The proof can also be found here....
7
votes
1answer
188 views

On prime numbers of the form $7\times10^n+69$ and the lights out puzzle

Consider those natural numbers $n$ such that $7\times10^n+69$ is a prime number. The first $15$ such numbers are $1$, $2$, $3$, $6$, $7$, $8$, $10$, $12$, $13$, $21$, $46$, $68$, $91$, $153$, and $366$...
7
votes
0answers
335 views

Yet an other conjecture about odd numbers $n=a+b$ such that $a^2+b^2$ is prime

This question is related to A conjecture about an unlimited path and Any odd number is of form $a+b$ where $a^2+b^2$ is prime but I present it on its own if anyone would like to help finding ...
7
votes
1answer
343 views

Asymptotic Distribution of Prime Gaps in Residue Classes

Define $\pi_{n,a}(x)$ as the number of primes $p$ less than $x$ such that $p\equiv a\bmod n$ for coprime $n,a$. This function can be asymptotically approximated by $$\pi_{n,a}(x)=\frac{\operatorname{...
7
votes
0answers
113 views

If prime $p=a_n10^n+a_{n-1}10^{n-1}+\ldots+a_110+a_0$ then $f(x)=a_nx^n+\ldots+a_0$ is irreducible in $\mathbb{Z}[x]$

I have been trying to solve this problem on my own for four days now, and I cannot figure out how to prove it: If we express a prime $p$ in base $10$ as $$p= a_m10^m+a_{m-1}10^{m-1}+\ldots +a_110+a_0,...
7
votes
0answers
147 views

Can we prove this conjecture concerning Pell equations?

For every positive integer $n$, not being a perfect square, denote the fundamental solution of the Pell equation $$x^2-ny^2=1$$ with $(a,b)$. In other words, $b$ is the smallest positive integer such ...
7
votes
0answers
272 views

What's infinte sum of the reciprocal of the primorial?

$$\sum_{n=1}^\infty \frac{1}{p_n\#} = \frac{1}{2}+\frac{1}{2\times3}+\frac{1}{2\times3\times5}+\dots$$ where $p_n\#$ is the nth Primorial. Does this sum approaches some known value or constant and ...
7
votes
0answers
78 views

Prove there are infinitely many integer solutions to $z^z = y^y x^x$ for with $x,y,z > 1$

I have tried a number of methods using prime factorisations but they inevitably lead to invoking too many unknowns for me and balloon in complexity.
7
votes
0answers
142 views

Is $\sum_{n=1}^\infty \ln \left(1-\frac{1}{p_n^s} \right)=-\ln \zeta(s)$ the only known series with primes and nontrivial closed form?

To clarify, I'm asking about series where $n$th term depends only on $n$th prime number. From the famous result (by Euler, I think) we have: $$\sum_{n=1}^\infty \ln \left(1-\frac{1}{p_n^s} \right)=-\...
7
votes
0answers
129 views

What is known about the counting function of Gaussian primes"

The counting function of primes among $\Bbb{N}$, describing the asymptotic density of the primes, is well known (the Prime Number theorem). Let's define a mild generalization of the counting function ...
7
votes
0answers
121 views

Number Theory: $\binom{p-1}{k} \equiv (-1)^k \pmod{p}$

I have this problem assigned for homework: Prove that if $p$ is an odd prime and $k$ is an integer satisfying $1<k<p-1$, then $\binom{p-1}{k} \equiv (-1)^k \pmod{p}$. I've come up with a proof ...
7
votes
0answers
245 views

Where is The third Gisella prime?

A Gisella prime is a prime number obtained from concatenating the first $n$ natural numbers starting from $2$ and then replace each composite on that concatenation with the concatenation of its prime ...
7
votes
0answers
110 views

Applying iterated function on the sum of the squares of the prime factors of $30$

Let $f(n)$ denote the sum of the squares of the prime factors of $n$ with multiplicity. For example, $f(60)=f(2\cdot2\cdot3\cdot5)=2^2+2^2+3^2+5^2=42$. Denote the iterated function $f^k(n)=\...
7
votes
0answers
193 views

The Existence of “Simple” Prime Generating Functions

Obviously, we do not know an explicit and easily manipulable formula for finding every prime - that is, a function $f(n)$ which yields the $n^{th}$ prime. I've seen plenty of formulas that "cheat" in ...