Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

1
vote
1answer
43 views

How to compute Dirichlet densities?

I need to calculate the Dirichlet density of the set of primes $p$ of the form $p = n^2 +1$ (in fact show it is zero), but I have no idea how to go about it. My definition of Dirichlet density of a ...
0
votes
1answer
26 views

Mathematical terminology for primes $(q+1)/2$ such that $q$ is also prime

So I know that if both $p$ and $2p + 1$ are primes, then $p$ is a Sophie Germain prime from the Prime Glossary. My question is this: How do we call a prime $r=(q+1)/2$ such that $q=2r-1$ is also ...
1
vote
0answers
27 views

Number of squarefree numbers and the Basel problem

Who discovered/proved that there are about $$ \frac{x}{\zeta(2)} $$ squarefree numbers up to $x$, or (roughly) when was this first known? Today I think this is considered 'obvious', but I don't know ...
1
vote
0answers
11 views

A Mertens-like product over primes

MathWorld's page Prime Products gives the 'related result' (7) to Mertens' theorem: $$ \lim_{n\to\infty}\log p_n\prod_{k=1}^n\frac{1}{1+1/p_k}=\frac{\pi^2}{6e^\gamma}. $$ Does this identity have a ...
1
vote
1answer
27 views

Is there a probabilistic prime test with time complexity $log^p (p\lt 1)$?

My question is: Is there a (possibly probabilistic) prime test with sub-logarithmic runtime complexity? Is it possible to construct one? I have found the following complexities for the most common ...
3
votes
2answers
35 views

$\forall n\ /\ \not\exists$ {primitive roots modulo n}: if $\ Max(ord_n(k))+1 \mid n\ $ then $\ Max(ord_n(k))+1\ $ is prime?

When a number $n$ does not have primitive roots modulo n, $Pr(n)$, it is possible to generate the set $M$ of those numbers $m$ whose order $ord_n(m)$ is the maximum multiplicative order of $k$ in ...
22
votes
3answers
2k views

How to force prime numbers into a line?

Inspired by an article on Prime Spiral and Hough transform I tried to analyze patterns created by plotting numbers on spiral (Archimedean?). $$x = \cos( angle ) * radius$$ $$y = \sin( angle ) * ...
0
votes
1answer
109 views

Gaps between primes: bounds - a question of possibilty

Let $n$ be any given natural number. Let $p$ be the very next prime greater than $n$. Let $b$ be the bound for the prime gap above $n$. Here, the bound is strictly the limit from $n$ to $p$, meaning ...
1
vote
0answers
80 views

Conjecture: for even n without primitive roots modulo n, the set of $m \in Max(ord_n(k))$ contains one pair of primes $p_1+p_2=n$ (Goldbach)

Conjecture: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ contains at least a pair of primes ...
0
votes
0answers
14 views

system of congruency prime solutions

If you have a system of congruency and you have the solution space. Is there criteria to determine if there is a prime in the solution space and if yes is there a better way to find them instead of ...
0
votes
1answer
30 views

If $N\equiv 1\pmod 4$ does then follow that $p\equiv q\equiv 1\pmod 4$

$N = pq$ is the product of two primes. If $N\equiv 1\pmod 4$, does then follow that $p\equiv q\equiv 1\pmod 4$ ?
2
votes
1answer
85 views

Special representation of a number

How can I check, if a number $n$ can be representated by $$pq+rs$$ where $p,q,r,s$ are pairwise different prime numbers with the same number of digits. For example, $$105153899965560312960 = ...
3
votes
1answer
28 views

Matrix with prime entries and largest possible determinant

Let $n\ge 1$ be a natural number. Arrange the first $n^2$ primes in a $n\times n$-matrix, such that the determinant becomes as large as possible. What is the largest possible determinant and which ...
13
votes
2answers
335 views

Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime

While I was studying Euler's Totient function, $\varphi(n)$, I stumbled upon the marvelous book "Index to Mathematical Problems, 1980-1984" By Stanley Rabinowitz. In this page of the book (link to ...
4
votes
0answers
137 views

About the total number of twin primes in the vicinity of twin primes

Just for curiosity's sake, I did a test regarding twin primes, and I have doubts about the meaning of the results. Test: calculation of ${\pi_2}$(n) and the twin primes density in the vicinity of ...
4
votes
1answer
45 views

Is there a counterexample? $\forall p \in \Bbb P\ ,\ p\gt 61\ ,\ \exists\ r1,r2\ \in \{\ Primitive\ Roots\ Modulo\ p\ \}\ /\ r1+r2 = NextPrime(p)$

This is the weirdest thing I have observed so far! Take the set of Primitive Roots Modulo p (link to definition here) of a prime number $p$, $Pr(p)$. For those primes $p \gt 61$ there is always a pair ...
0
votes
0answers
20 views

Counting the number of elements $x$ between $p$ and $p^2$ where lpf$(x(x+2))=7$

Let $p > 7$ be any prime. Let $f_7(p)$ be a function that counts the number of elements $x$ where $p < x < p^2$ and lpf$(x(x+2))=7$ where lpf is the least prime factor. It has been ...
3
votes
2answers
243 views

Fastest way to find if a given number is prime

Given a random number, what would be the quickest possible way of finding out whether it was prime? Obviously, one could just iterate through the number in order to see if it was divisible by ...
22
votes
6answers
5k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
3
votes
0answers
96 views

Conjecture concerning sums of reciprocals of largest prime factors

Let $x$ be an integer, $r(x)$ the reciprocal of the largest prime factor of $x$. Let $f(n) = \sum_{k=1}^{n-1} r(k) r(n-k)$ for which $k$ and $(n-k)$ are coprime. For $n = 3 \dots 10$, $f(n) = ...
2
votes
3answers
83 views

Is a prime to the power of a fraction always irrational?

Let $p$ be a prime number and let $x$ be a faction, i.e. $x \in \mathbb{Q} - \mathbb{N}$. It seems to be the case that $p^x$ is always irrational. How do I prove this?
0
votes
4answers
55 views

Prove or disprove $\frac{\left(2^{p}-2\right)}{p}\ \in \Bbb N, \forall\, p,\, prime$

Apologies in advance for poor formatting, not completely accustomed to typeset. What I ask is any non-particular value p, with one condition that it is prime, for which to disprove the following ...
-6
votes
3answers
115 views

Is this the real reason why 1 is not prime? [duplicate]

Divisibility by 1 is misleading as it does not divide a number into smaller parts. If divisibility by 1 is disallowed, then: The Unit: A whole number that is indivisible. Prime: A whole number that ...
3
votes
1answer
48 views

Is this reasoning correct for average prime gap?

Since \begin{align} &\operatorname{li}(n)\sim\Pi (n)\equiv\sum _{k=1}^{\lfloor \log (n)\rfloor } \frac{\pi \left(n^{1/k}\right)}{k}\\ \end{align} then the average gap for \begin{align} ...
0
votes
0answers
43 views

Looking for a function which can serve as an upper bound to a count of the the pairs (x)(x+2) that have a given least prime factor?

Let $p \ge 7$ be a prime. Let $z > p$ also be a prime. Let $f_p(z)$ be the number of elements $x$ such that $z \le x < z^2$ and the least prime factor of $x(x+2) = p$ I am trying to find ...
0
votes
0answers
43 views

Solve an equation of the prime counting function

The problem is, Find all the positive integral values of $x$ for which we have, $$\pi(p_n-x)=\pi(p_{n+1}-x-1)$$where $\pi(x)$ denotes the number of primes not exceeding $x$. I don't know where ...
0
votes
1answer
30 views

Notation about factors

What is the name (if there is one) of the "full factorization representation" of a number, in which also the powers of the factors are (recursively) decomposed until all the numbers used in the ...
0
votes
4answers
2k views

Co Prime Numbers less than N

I need to find all the numbers that are coprime to a given $N$ and less than $N$. Note that $N$ can be as large as $10^9.$ For example, numbers coprime to $5$ are $1,2,3,4$. I want an efficient ...
2
votes
2answers
51 views

prime number problem:

How can I show that; For any prime $p,$ there exist $u, v\in\mathbb{N}\setminus{\{p\}}$ ( and depend on $p$) such that $\color{Purple}{p\mid uv}$ and both ...
0
votes
2answers
47 views

Let $p$ be a prime. Prove that $\sum_{i=0}^{p}\binom pix^i \equiv x + 1 \pmod p$

Let $p$ be a prime. Prove that $\displaystyle\sum_{i=0}^{p}\binom pix^i \equiv x + 1 \pmod p$. i got \begin{align} & \frac{p!}{i!(p-i)!}(x^0+x^1+x^2+x^3+x^4+\cdots+x^p) \\[4pt] = {} & ...
4
votes
1answer
62 views

A consequence of the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$

Assume that the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$ holds for all integers $x,y>2$ where $\pi(x)$ denotes the number of primes less than or equal to $x$. Then find all $m$ and $n$ such that, ...
1
vote
1answer
34 views

Is this bullet really needed in Furstenberg's proof of infinitude of primes?

See here . The bullet I'm referring to is: Any union of open sets is open: for any collection of open sets $U_i$ and $x$ in their union $U$, any of the numbers $a_i$ for which $S(a_i, x) \subset ...
2
votes
1answer
75 views

$\prod_{ p\leq x}p\leq 4^{x-1}$ for all real $x\geq2$

How you prove this? I'm looking the Erdös proof from Bertrand Postulate and there are many things I don't get. Please don't hints, I'm newbie in combinatorics techniques. In the book I don't get ...
3
votes
1answer
90 views

Conjecture about the product of the primitive roots modulo a prime number ($\prod Pr_p$)

While I was learning about the primitive roots modulo $p \in \Bbb P$ (I will call $Pr_p$ to the complete list of the primitive roots module $p$) and having in mind the conjecture explained in this ...
2
votes
0answers
37 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
0
votes
1answer
31 views

Diffie Hellman: Subgroup Confinement Attack

how can I solve the following tasks? a) Find all primitive elements of $\mathbb{Z}_{37}$. I guess the only possibility here is to try if the remainder off all elements from 1 to 36 to the power ...
-1
votes
0answers
33 views

Let p be a prime. Prove that $\sum_{i=1}^{p}({a}/{p})x^i \equiv x + 1 \pmod p$ [closed]

Let $p$ be a prime. Prove that $\sum_{i=1}^{p}({a}/{p})x^i \equiv x + 1 \pmod p$ I'm lost on this one. Any help would be appreciated
1
vote
1answer
32 views

A question on Primes in Arithmetic Progression

We know that an arithmetic progression has to have a composite number since there are arbitrarily large gaps between primes. But I was wondering whether the following construction is possible: Can ...
1
vote
0answers
57 views

Problem with multivaluedness of $(-1)^{\frac 14}$

Assume that $p\equiv3\mod4$ is an odd prime and $k$ an odd number. Then $$m=(-1)^{\frac{p^k-p^{k-1}+2}{4}}$$ seems to be always the value $1$ (?). This would be interesting how one can prove this - I ...
1
vote
0answers
25 views

Estimating the number of elements with a given least prime factor in a sequence of consecutive integers

Let $a,n$ be any positive integers. Let $\varphi(x)$ be the Euler totient function. It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will ...
3
votes
1answer
132 views

Is there a way to relate prime numbers and the fourier transform

According to what I know about Fourier transforms, any continuous periodic signal can be represented as a combination of sine and cosine functions. To me, this looks analogous to the "Fundamental ...
-1
votes
1answer
150 views

Integer linear combinations of coprime integers

Consider the finite set $S=\{s_1,s_2,\dots,s_n\}$ such that $GCF(s_1,s_2,\dots,s_n)=1$. Show that $\exists n$ such that $n$ cannot be written as $n=c_1s_1+c_2s_2+\dots+c_ns_n \forall c_i,s_i \in ...
1
vote
2answers
32 views

A question on perfect square

Prove that if $ab$ is a perfect square and $\gcd(a,b)=1$, then both $a$ and $b$ must be perfect squares. Their Answer: Consider the prime factorization $ab=p_1^{e_1}\cdots p_k^{e_k}$. If $ab$ ...
0
votes
2answers
79 views

Fermat little theorem : show that if $p$ is prime, then $a^p \equiv a\pmod p$ holds, if $p$ divides $a$.

Fermat little theorem : show that if $p$ is prime, then $a^p \equiv a \pmod p$ holds,if $p$ divides $a$. I know it doesn't hold but I'm having a hard time proving it.. I know that if $p$ divides ...
0
votes
3answers
151 views

Proving prime number combinatorics

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, ...
4
votes
2answers
32 views

Property of the sequence of primes

Let $p_n$ denote the $n$-th prime number. Does anyone know a proof of the following property? $$\forall n, n', \ p_n p_{n'} \geq p_{n+n'}$$ I'm surprised I can't find anything on this while I ...
5
votes
3answers
50 views

$a^{13} \equiv a \bmod N$ - proof of maximum $N$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 ...
3
votes
1answer
64 views

The number of primes in an interval

What is the smallest known $c$ so that for any $n\geq 2$ there are at least $n/\log_2{n}$ primes between $n$ and $cn$ (inclusive)? The prime number theorem seems to give an asymptotic result so I am ...
1
vote
1answer
91 views

What is the next prime number?

Given an integer \begin{equation*} N~\text{such that}~N\leq 10^{18}, \end{equation*} what is the next prime number after this number? What approach should I use to solve this problem? (Problem ...
9
votes
2answers
224 views

Yet another conjecture about primes

Let $\mathcal{N}(n)$ be the next prime greater than $n$. Conjecture: $\mathcal{N}(n!)-n!\:$ is either $1$ or a prime. It holds for n=1 to 99 and the expression is 1 for 3,11,27,37,41,73,77 and ...