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
4
votes
2answers
124 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
85 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
66 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
66 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, $...
0
votes
2answers
99 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
72 views

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

I've heard there are elements of Sieve Theory and whatnot but no further 'outline' of how he proved the theorem.
3
votes
2answers
212 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
51 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
88 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
68 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 ...
1
vote
0answers
59 views

Solutions of $x^n=a$ modulo primes.

Let $p$ be an odd prime and $a$ be an integer that is not a perfect square. We can impose a congruence condition on $p$ that guarantees the equation $x^2=a \pmod p$ does not have a solution. For ...
10
votes
1answer
103 views

Is the following always prime?

For a given $k$ define $$s_k = 1 + \prod_{i=1}^k p_i$$ $$t_k = \text{NextPrime}(s_k)$$ $$v_k = t_k - s_k +1$$ Where $p_i$ is the $i$th prime number. Conjecture: $v_k$ is prime Example: $$k=3$$ $$...
0
votes
0answers
31 views

Ordering sequences of prime decompositions

C.f. Engel's Problem Solving Strategies; p. 132, #33: Out of $n+1$ integers $\leq 2n$, find $p,q$ s.t. $p|q$. Rather than soliciting a solution I'm wondering if there's a way I can make my attempt ...
3
votes
0answers
66 views

Are there forced factors of numbers of this kind?

Let $$f(n):=n^{n^2}+(n+1)^{(n+1)^2}$$ for a positive integer $n$. For clarification $n^{n^2}$ means $n^{(n^2)}$ , analogue for the other summand. Can we find a concrete factor of $\ f(n)\ $ (like ...
25
votes
1answer
777 views

What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?

What is known about the asymptotic order and/or lower and upper bound of the sum of the binomial coefficients $$ S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p} $$ where the ...
3
votes
0answers
53 views

Complex numbers $z$ such that $n-z$ and $n+z$ are Gaussian primes

Is it known whether for all large enough positive integer $n$, there exists a complex number $z$ such that $\vert z\vert<n$ and both $n-z$ and $n+z$ are Gaussian primes? If yes, are there results ...
1
vote
1answer
44 views

Is it true that for all large enough integer $n$, there is a integer $m$ such that $n+im$ is a Gaussian prime?

Let $n$ denote a positive integer greater than $6$. Is it known whether there is always an integer $m$ such that $n+im$ is a Gaussian prime?
6
votes
2answers
2k views

Frequency of the Prime Numbers

Suppose I took all natural numbers less than or equal to $x$ and I picked one at random. Is there a way that we know of to express the probability that my number is prime in terms of $x$, for all $x$? ...
0
votes
0answers
33 views

Use a pairing function for prime factorization

Let $n$ be the product of the two unknown primes $a$ and $b$ ($a < b$): $ab = n$ My idea was to use a pairing function so: $a = f(p)$ and $b = g(p)$ Then the equation is: $f(p) \cdot g(p) = n$ ...
26
votes
3answers
701 views

Does there exist positive rational $s$ for which $\zeta(s)$ is a positive integer?

Does there exist positive rational $s$ for which the Riemann Zeta function $\zeta(s) \in N$ or equivalently, does there exist finite positive integers $\ell,m$ and $n$ such that $$\zeta\left(1+\dfrac{\...
3
votes
1answer
42 views

First few smallest Carmichael numbers congruent to $11 \pmod {12}$

There are known to be infinite Carmichael numbers congruent to $a\pmod b$ for coprime integers $a$ and $b$. There are plenty of examples of small Carmichael numbers congruent to $1, 5, 7 \pmod {12}$, ...
12
votes
6answers
8k views

prime divisor of $3n+2$ proof

I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof I tried saying by the division algorithm the prime factor is either the form 3m,3m+1,3m+...
1
vote
1answer
56 views

CRT on prime vector

I have a question that intrigue me: Given primes and some reminder vector P=primes(13)=[2 3 5 7 11 13] R=[1 2 1 3 9 11] (R=mod(1571,P)) What option do i have ...
17
votes
3answers
534 views

How to make a pair of six-sided dice whose sum is always a prime number?

In other words, how can I find two sets of six distinct integers $a_1, \dots, a_6 \in \Bbb Z$ and $b_1, \dots, b_6 \in \Bbb Z$ such that $a_i+b_j$ is prime for any $i, j \in \{1, \dots, 6\}$?
4
votes
8answers
208 views

Proof that $\sqrt[3]{17}$ is irrational

Consider $\sqrt[3]{17}$. Like the famous proof that $\sqrt2$ is irrational, I also wish to prove that this number is irrational. Suppose it is rational, then we can write: $$ 17 = \frac{p^3}{q^3}.$$ ...
4
votes
0answers
98 views

How many divisors of $\phi(m)$ do not divide $m-1$?

Lehmer's totient problem asks if there exists a composite number $m$ such that $\phi(m)$ divides $m-1$. Lower bounds on $m$ has been established but we do not know if a solution exists. Clearly, if we ...
3
votes
1answer
56 views

How dense are primes congruent to 1 and 3 (mod 4)? [duplicate]

There are infinitely many primes of the form $4n+1$ and $4n+3$. In a given interval $[0,N]$ for a large enough $N$ do we expect to see the same number of primes congruent to $1$ and $3$ (mod 4)?
1
vote
1answer
96 views

Is there an Efficient Way to Divide by a Mersenne Prime?

Mersenne primes are used in Computer Science and Cryptography because they support fast modulo computation. If $p$ is a Mersenne prime, $n \bmod p$ can be computed with just a few add and shift ...
0
votes
0answers
111 views

Wolstenholme Number

A Wolstenholme number is the (reduced) numerator of the fraction $1+{1\over4}+\cdots+{1\over n^2}$. The first few are $1, 5, 49, 205, 5269, 5369, 266681, 1077749$. Are there Wolstenholme numbers that ...
3
votes
1answer
64 views

Question on Divisor Sum over the Liouville Function $\lambda(d)=(-1)^{\omega(d)}$

This question assumes the following: $\nu(n)$ is the number of distinct primes in the factorization of $n$, $\omega(n)$ is the number of prime factors counting multiplicities in the factorization of $...
3
votes
4answers
222 views

Can anyone come up with an interesting consequence of the Twin Prime Conjecture being true?

The question is in the title. Was wondering if there are statements equivalent to or a consequence of the statement that there are infinitely many twin primes. If not, then why is this conjecture a "...
1
vote
0answers
80 views

Unique pattern in addition of digits

Problem: For positive integers $n,k$, let $$S(n,k)=\sum_{i=1}^{n}i^k$$ and for positive integers $m,b$, with $b>1$, let $D(m,b)$ be the sum of the base-$b$ digits of $m$. Q$1$- Show that ...
1
vote
1answer
62 views

How many times are these three quantities simultaneously prime?

For recreation, I would like to count the number of times the path length, "area above," and area below the prime counting function, are simultaneously prime. The following function is used to count ...
2
votes
0answers
116 views

If $n = 18k+5$ is composite, there are at least 9 divisors of $\phi(n)$ which do not divide $n-1$.

If $n$ is a composite of the form $18k+5$, there at least 9 divisors of $\phi(n)$ which do not divide $n-1$. Is this true in general or if not, what is the smallest counter example? Update: No ...
3
votes
2answers
117 views

If $p\equiv 3\pmod{4}$ is a prime, then $\frac{p-1}{2}! \equiv \pm1 \pmod p$

If $p\equiv 3\pmod{4}$ is a prime, then $\frac{p-1}{2}! \equiv \pm1 \pmod p$. I don't know how to prove this statement. $p=4m+3$, so $(2m+1)! \equiv \pm1\pmod p$ This is all I did.
6
votes
1answer
3k views

Prove the converse of Wilson's Theorem

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime. This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
2
votes
2answers
1k views

$(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$

The Wiki page on Twin Primes says The pair $(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$. This is obviously connected to Wilson's Theorem. Can anybody provide a proof for ...
3
votes
1answer
41 views

(m,m+2) is twin prime, iff 4((m−1)!+1)≡−m(mod m(m+2))

I'm a programmer, a newbie on math. I'm trying to code to list twin prime. I've found this: $(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$ The pair (m, m + 2) is twin prime,...
14
votes
1answer
707 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 1

I was reading "The Prime Numbers and Their Distribution" by Gérald Tenenbaum and Michel Mendès France, the section about Cramér's Model, and I couldn't prove a couple of results. I would like to start ...
4
votes
2answers
366 views

$(p\!-\!1\!-\!h)!\,h! \equiv (-1)^{h+1}\!\!\pmod{\! p}\,$ [Wilson Reflection Formula]

Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$. I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$ My first thought is that by ...
3
votes
2answers
240 views

$MATHS\times7=POISON$ where $MATHS$ is a prime

Today, when I was doing a past paper for my upcoming competition, I found a interesting but hard problem: In the equation below, each letter represents distinct digits from $0$ to $9$. $$MATHS\...
0
votes
0answers
33 views

How to prove that $r_{0}(n)/n<1/2$?

Under Goldbach's conjecture, define for a large enough integer $n>n_0$ the quantity $r_{0}(n)$ as $\inf\{r\geqslant 0,(n-r,n+r)\in\mathbb{P}^{2}\}$. Is it possible to prove that $\forall n>n_{...
4
votes
1answer
83 views

Proof of the theorem

I have been unsuccessful in trying to find a proof of this theorem the name of which, if existing, I don't know. For any prime number $p$ and natural number $A$, where $p$ doesn't divide $A$, the ...
26
votes
0answers
858 views

Does the average primeness of natural numbers tend to zero?

Note 1: This questions requires some new definitions, namely "continuous primeness" which I have made. Everyone is welcome to improve the definition without altering the spirit of the question. Click ...
2
votes
0answers
69 views

Unique variance conjecture: The ratio of a number to the variance of its divisors is injective

The variance $v_n$ of a natural number $n$ is defined as the variance of its divisors. There are distinct integer pairs whose variances are equal; the smallest such pair is $(691, 817)$. However I ...