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.

Filter by
Sorted by
Tagged with
1
vote
2answers
30 views

Remainder of Fermat's little theorem sum

With p being a prime number, what is the remainder of $$\sum_{k=1}^{p-1} {k^{p-1}}$$ divided by p ? I know that Fermat's little theorem states that for a prime number p, and a number A that is not ...
44
votes
0answers
840 views
+100

Can we remove any prime number with this strange process?

This is a little algorithm I made today, which may appear to be quite complex, so I will start with an example. Questions are at the end of the post. The process goes as follows: Start with the ...
-2
votes
0answers
56 views

Maximum $k$ for odd consecutive primes $p,q$ and $q-p=2k$ for $1$ to $k$ [on hold]

For consecutive odd primes $p, q$ with $q-p=2\cdot k$ for consecutive numbers $1$ to $k$, is some maximum $k$ known? Is there a table showing at what least prime each gap occurs? Thus one would want ...
-2
votes
1answer
147 views

What is $\frac{1}{p}$ mod p?

In a multiplicative group $0$ doesn't have an inverse. But is $1/p \bmod p = 0$ or is $1/p \bmod p$ undefined? I wondered if you can argue that $$\begin{align}1/p &\equiv p^{-1} \\ &\equiv p^...
1
vote
1answer
57 views

Evaluating this sum. Is there a closed form?

Trying to evaluate this sum: $$ S=\sum_{n=1}^\infty \ln(p_n^2)K_1(\ln(p_n^2)). $$ Here $p_n$ is the nth twin prime and $K_1$ is the modified bessel function of the second kind. So one should be ...
4
votes
3answers
103 views

Prime counting function; is it true that $\pi(n - m) \geq \pi(n) -\pi(m)$?

Let $\pi$ be the prime counting function, and $m, n$ positive integers, $n > m > 1$. Is it proven that $\pi(n - m) \geq \pi(n) -\pi(m)$ ?
0
votes
1answer
54 views

Find all integers $x$ such that $2^p + 3^p = x^2$ where $p$ is prime

Find all integers $x$ such that $2^p + 3^p = x^2$ where $p$ an arbitrary prime number. I think that this equation has no solution. Thank all for help!
1
vote
0answers
51 views

Conjecture on Prime Numbers and Exponential Equipment

How to generate a rigorous proof for - The specific conjecture which states that we can always frame every Prime number in an exponentially framed equation with perfect cubes & squares. I'll ...
1
vote
1answer
25 views

Continuation of the Riemann Prime Counting function

Let $f(x)=\sum_{n=1}^{\lfloor \ln(x)\rfloor} \frac {\pi(x^{\frac 1n})}n$ ($\pi(x)$ is the Riemann prime counting function, here are some more informations). It is thanks to Riemann well known that $\...
1
vote
1answer
40 views

Generalization of digit-wise divisibility lemmas [duplicate]

Background In undergraduate Abstract Algebra homework, for an integer $n$ with decimal representation $a_m a_{m-1} ... a_1 a_0$, I proved that $3$ divides $n \iff 3$ divides $\sum_{i = 0}^{m} a_i$, ...
3
votes
1answer
66 views

Confusing thing at the proof of proth theorem

$Proth$ $theorem$ simply depends on a result which proved by pocklington ; The result says : Let $N-1=q^nR$ where $q$ is prime, $n\ge1$ , and $q$ doesn't divide $R$. Assume that there exists an ...
1
vote
1answer
44 views

Are Wieferich primes Wieferich numbers?

In the article 'On a conjecture of Crandall concerning the $qx+1$ problem' by Franco and Pomerance, they define Wieferich primes to be prime numbers $p$ for which $p^2|2^{p-1}-1$ and Wieferich numbers ...
1
vote
1answer
49 views

Is there a set of primes such that the union of their multiples occurs with frequency $1/n$, where $n$ is an integer?

Are there two or more primes, $p_1, p_2, \ldots$ such that the union of their multiples occurs with frequency $1/n$, where $n$ is an integer? If so, can that n be prime? I put it into a computer and ...
16
votes
1answer
439 views

An interesting algorithm about prime numbers that I thought today

I thought up the following algorithm today: Choose $a_1\in\mathbb{Z}^+\setminus\{1\}$. Then let $a_{n+1}=a_n+p_n$, where $p_n$ is the largest prime factor of $a_n$. The algorithm is easy, but I ...
7
votes
3answers
177 views

Why such an interest for the error term in the Prime Number Theorem

I have some issues when dealing with people working outside number theory, to motivate and justify in some sense the problems I am interested in. Mainly, here are the issues I do not know enough ...
2
votes
1answer
88 views

Error term of the prime number theorem on GRH?

I know that under GRH we have $$ \sum_{\substack{1 \leq n \leq X \\ n \equiv a (q) }} \Lambda(n) = \frac{X}{\phi(q)} + O(X^{1/2} (\log X^2)). $$ From this I would like to deuce a abound for $E$ ...
4
votes
0answers
158 views
+50

show that $n\Upsilon_{n-1} \equiv -1 (mod\ n)\ \ \ \ \ \iff \ \ n\ is\ prime $

The Bernoulli numbers $B_n$. where all numbers $B_n$ are zero with odd index $n>1$. first values are given by $B_{0} = 1$ , $B_{1} = -1/2$, $B_{2} = 1/6$, $B_{3} = -1/30$. Agoh conjecture: let $...
3
votes
2answers
46 views

Limit involving prime and composite numbers

Can someone help me to figure out what $$\lim_{n\to\infty} \frac {c_n}n-\frac{c_n}{p_n}-\frac {c_n}{n^2}$$ is equal to? I am pretty sure its $1$ and i tried many different things but i couldnt figure ...
54
votes
3answers
2k views

Is $29$ the only prime of the form $p^p+2$?

I searched for primes of the form $p^p+2$, where $p$ is prime for a range of $p \le 10^5$ on PARI/GP and found that 29 is the only prime of this form in this range. Questions: $(1)$ Is $29$ the ...
15
votes
2answers
353 views
+50

Conjecture: “For every prime $k$ there will be at least one prime of the form $n! \pm k$” true?

Using PARI/GP, I searched for primes of the form $n!\pm k$ where $k \ne 2$ is prime and $n\in \Bbb{N}$. With the help of user Peter, we covered a range of $k \le 10^7$ and couldn't find a prime $k$ ...
1
vote
1answer
33 views

Limitations on the difference of coprime composites less than $n^2$ for ascertaining primality?

Let $q$ be a prime where $n < q < n^2$. Let $p_1, p_2, \ldots, p_k$ be all the primes $\leq n$. Is it true that for any $q$, you can find two numbers $a,b$ where $a+b=q$ or $a-b=q$, such that $...
4
votes
2answers
2k views

What's the best software for primality tests of huge numbers? (check if an integer is prime or not)

I just read an article about huge prime numbers (some with more than 10millions digits!) that are discovered using software that check if an integer is prime or not (primality test sofwares). What is ...
1
vote
3answers
66 views

How to prove 1111…11 (91 digits) is a prime or composite number? [duplicate]

How to prove $1111......11$ ($91$ digits) is a prime or composite number? My Approach: $1111......11$ can be expressed as $10^{0}+10^{1}+10^{2}+...…..+10^{90}$ Using summation of a geometric ...
5
votes
2answers
114 views

Maximum runs of composites in arithmetic progressions

Is there a proof that every arithmetic progression of gap $p$ has a prime in the interval $[p, p^2)$? Put another way, can you prove the following: For all primes $p$, and all integers $0 \le m <...
9
votes
1answer
141 views

Prove that $n^k+1$ has a prime divisor $>2k$

Let $n\ge3$ & $k\ge2$. Show that $n^k +1$ has a prime divisor $>2k$.
1
vote
2answers
82 views

Prove $r$ the smallest quadratic non-residue modulo $p \geq 3$ is prime

I've been struggling to find the solution for this question for a while now and thought I might as well ask for some help. The question is: Let $r$ be the smallest positive quadratic non-residue ...
2
votes
0answers
159 views
+50

Prime number and Relationship of Sequences of period 4,5,and 6

Let $p$ be a prime number.($p \neq 2,3,5$) Let $t^+,t^-,a$ be sequences. $t^+_{k+5}=t^+_k,t^+_1=0,t^+_2=-1,t^+_3=-1,t^+_4=0,t^+_5=2$ $t^-_{k+5}=t^-_k,t^-_1=-1,t^-_2=0,t^-_3=0,t^-_4=-1,t^-_5=2$ $a_k=...
2
votes
0answers
43 views

$π(x+y) - π(x) ≤ c·y/\ln(y)$ for some constant $c$?

Thinking about the prime number theorem, I wondered whether it is known that there is some constant $c$ such that $π(x+y) ≤ π(x) + c·y/\ln(y)$ for every integers $x,y > 1$. I read that experts ...
1
vote
2answers
96 views

Construction of an exact function for counting primes in intervals.

I have constructed an exact function for counting primes in intervals and am curious to know if it 1) has any importance? 2) Has been derived already? I have no formal education in number theory, and ...
4
votes
2answers
104 views

Prime Zeta function at 1

I wanted to find $$\lim_{s\to 1} (P(s)-\ln(\zeta(s)))$$ and here is my attempt: So we know that $$M=\gamma +\sum_{n=2}^\infty \mu(n) \frac {\ln(\zeta(n))}{n}$$ and that $$P(s)=\sum_{n=1}^\infty \mu(...
1
vote
1answer
36 views

Solving a linear equation in one component of $\Bbb{Z}^3$.

Consider the space $X = \Bbb{Z}^3$, a $\Bbb{Z}$-module. Let $M = \{ \sum_{i=1}^n c_i(p_i, q_i, r_i) : \sum_{i=1}^n c_i q_i = 0,$ where $p_i, q_i, r_i$ are either prime numbers or $0 \}$. Then is $M ...
2
votes
2answers
114 views

What number representation is this?

If $p$ is a positive prime number, put $p! = \textrm{lcm}(2, 3, 5, \dots, p) = p\cdots3\cdot2$. Then every non-negative integer can be written uniquely as: $x_1 + 2\cdot x_2 + 3\cdot 2 x_3 + \dots + ...
1
vote
2answers
95 views

If there exist infinitely many $x \in \mathbb{Z}:3x^2+3x+1 = 3p-2$ for $p \in \mathbb{P}$, show there exist infinitely many $y:3y^2+3y+1$ is prime

Assume there exist infinitely many $x$ such that: $$3x^2+3x+1 = 3p-2$$ Where $p$ is prime. Can it be shown there exist infinitely many $y$ such that: $$3y^2+3y+1=q$$ Where $q$ is prime? I believe ...
1
vote
0answers
29 views

Is there any simplification to:$\mod(P_{k-1}\# \cdot J , \; P_k )\quad$?

Is there any way to simplify or to find pattern in: $$\mod(P_{k-1}\# \cdot J , \; P_k ) \quad with\quad J=0:P_k-1 $$ Sorry for not being clear at notaion, i will try to do it by example: $P_k=...
15
votes
1answer
1k views

The Goldbach Conjecture and Hardy-Littlewood Asymptotic

A source I am reading refers to the Goldbach conjecture (that every even number is the sum of two primes), and then immediately follows with the "Hardy-Littlewood conjecture" that $\sum \limits_{n ...
4
votes
2answers
119 views

Every sufficiently large positive integer is the average of $n$ distinct primes for certain $n \geq 2$?

I want to generalize a stronger Goldbach's conjecture a little bit because that might help solve it. I was thinking: For all $n \geq 2$, every sufficiently large positive integer $x \geq b_n$ is ...
4
votes
2answers
83 views

Checking for prime constellation

How does one systematically check if a given configuration of prime numbers $p_1, p_2, ... p_n$ is the densest possible configuration of primes in the range $[p_1, p_n]$? (The densest configurations ...
5
votes
5answers
11k views

Get numbers that have only 2,3 and 5 as prime factors

I am given an integer N. I have to find first N elements that are divisible by 2,3 or 5, but not by any other prime number. ...
2
votes
0answers
62 views

Found a new way to do CRT on prime vector

I found a new way to do CRT on prime vector. Given prime list P, and some residuals R=mod(n,P) , for example: P=[2 3 5 7 11] R=[1 0 3 1 9] This matlab function ...
1
vote
5answers
65 views

How to apply CRT to a congruence system with moduli not coprime?

$x=1 \pmod 8$ $x=5 \pmod{12}$ 8 and 12 are not coprime, I could break it to: $x=1 \pmod 2$ $x=1 \pmod 4$ and $x=5 \pmod 3$ $x=5 \pmod 4$ But what are the next steps to solve it? By the way, $...
1
vote
2answers
91 views

Where can I download a full list of all primes below $10^{15}$?

I would like to do some computing on a large list of primes. Unfortunately my computer is not strong enough to quickly generate such a list, so I'm looking to download a file that already contains ...
2
votes
0answers
67 views

Is there a Lay-Mathematician explanation for the proof technique of Zhang's Theorem? [on hold]

I've heard there are elements of Sieve Theory and whatnot but no further 'outline' of how he proved the theorem.
3
votes
2answers
210 views

Behavior of integer recurrence $u_0\geq 2$, $u_{n+1}=d(u_n)^\alpha$, for $\alpha \geq 3$, where $d$ is the number-of-divisors function

Let $u_0\ge 2$ and $\alpha\ge 1$ integers. I'm trying to study the sequence $(u_n)_{n\ge 0}$ defined by : $$\forall n\ge 0,\quad u_{n+1}=d(u_n)^{\alpha}, $$ where $d$ is the number-of-divisors ...
10
votes
5answers
3k views

The Frobenius Coin Problem

I am asked to prove that: For integers $n, x,y > 0$, where $x,y$ are relatively prime, every $n \ge (x-1) (y-1)$ can be expressed as $xa + yb$, with nonnegative integers $a,b \ge0$. ...
2
votes
3answers
100 views

Solving congruences like $3^p\equiv 1\pmod{\! p}$, $p$ prime [order computation]

In particular, I've used python to brute-force results of $3^n-1\bmod{7} = 0$ but was hoping there is a more elegant method.
0
votes
0answers
48 views

Approximating $r_{0}(n)$ with an integral

I'm still trying to find a tight upper bound for the quantity $r_{0}(n):=\inf\{r\geq 0,(n-r,n+r)\in\mathbb{P}^{2}\}$. My idea is that one should have $\sum_{r=1}^{r_{0}(n)}\Lambda(n-r)\Lambda(n+r)\...
8
votes
2answers
1k views

Are there an infinite number of primes which are any multiple of $n$ apart? [closed]

Are there an infinite number of primes which are any multiple of $n$ apart? That is take $n\in \mathbb{N}$, then is there an infinite number of primes which are separated by $\textbf{any}$ of the ...
1
vote
1answer
84 views

Prime counting function formulas

Are there any elementary (including floor, ceiling, mod) representations of the prime counting function. Or one without an integral.
2
votes
2answers
57 views

Is the additive rational group $\mathbb{Q},+$ generated by $\frac{1}{p}$ where p is a prime?

So it is known that the additive group of rationals numbers $\mathbb{Q},+$ is generated by $\frac{1}{n}$ with $n \in \mathbb{N_0}$ so that: $$\mathbb{Q},+ =grp\{\frac{1}{n} | n \in \mathbb{N}\}$$ Now ...
5
votes
1answer
63 views

4 distinct integers with prime sum for each triple

Here is a nice high school olympiad math problem: Can you choose 4 distinct positive integers so that the sum of each 3 of them is prime? How about 5? It looks that just by looking at reminders mod ...