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

8,753 questions
0answers
26 views

### Index of Fibonacci primes and Lucas primes.

For an integer $n\geq 0$ let $F_n$ denote the $n$th Fibonacci number and let $L_n$ denote the $n$th Lucas number. It is known that $F_n$ is prime only if $n$ is prime or $n=4$. According to ...
0answers
38 views

### Efficient method to check whether the nearest prime has distance $d$ or more?

Suppose, a prime $\ p\$ is given. How can I check efficiently whether the distance to the nearest prime is $\ d\$ or more , if $\ d\$ is given ? My approach is to start with $\ c=2\$ and as ...
0answers
23 views

### Modulo division by a prime

UMAC includes a polynomial hash, which includes this operation: y = (k * y + m) mod p p is the largest prime which is less ...
2answers
67 views

### A Simple Proof of the FTA using only elementary theory?

By elementary theory, we mean avoiding as much number theory as possible. The exposition below is sketchy but the necessary details involve 'primitive' constructions, like using the fact that the ...
1answer
51 views

### Does this equation yield only primes?

Interested in solving this equation for $x$: $\exp\Big(\frac{n}{\ln(\pi(x))}\Big)=\pi(x)$ for $n=1,2,3,...$ For $n=1$ up to $n=9,$ I got $x=5,11,13,19,29,37,47,59,73.$ $\pi(x)$ is the prime ...
0answers
27 views

### necessary and sufficient conditions that a number being prime or prime of special form? [on hold]

I like to gather some statements about the properties of prime numbers or prime of the specific forms. For instance 1) A prime number is a whole number greater than 1 whose only factors are 1 and ...
2answers
38 views

### Geometric-like Sum over Primes

Is there a known way to evaluate sums of the form $$\sum_{p\text{ prime}} x^{p},$$ and are there any restrictions on the value of $x$ (e.g., $|x|<1$ for typical geometric series)? EDIT: The ...
1answer
50 views

### Can the minimum of two consecutive prime gaps become arbitary large?

Here : https://oeis.org/A023186 the so-called "Lonely primes" are shown. Let $$[a,b,c]$$ be a triple of consecutive primes and define $$d:=\min(c-b,b-a)$$ My question : Can we prove that $d$ ...
2answers
44 views

### When can a number be expressed as the sum of two squares?

I'v learnt from this site that a composite number $n$ can be expressed as the sum of two squares if and only if its prime factor do not contain a prime $p \equiv3 \pmod 4$ which is powered to even ...
1answer
30 views

### Algorithm generating subset of primes, can we classify which of them or estimate how large percent of primes are generated?

Assume I have following algorithm: Two lists of numbers, first starting at 2, second starting empty. We now follow rule: Add a number to first list which makes difference with latest number the ...
0answers
69 views

### Primes that divide integers of the form $n^2+1$ or $n^2+3$ [on hold]

A similar question is supposedly included in an open assignment so I have retracted my working.
5answers
270 views

### Why probability of picking a random prime is 0? [duplicate]

"It's well known that there are infinitely many prime numbers, but they become rare, even by the time you get to the 100s," Ono explains. "In fact, out of the first 100,000 numbers, only 9,592 are ...
0answers
36 views

### Is the average deviation of a composite number unique?

Let $s_n$ be the standard deviation of the divisors of the natural number $n > 1$ then, $\dfrac{s_n}{n}$ is injective over composites. In other words, there does not exist composite numbers $m$ ...
1answer
24 views

### Proving that every non-zero prime element can be written as a power of g

Let $p\geq 2$ be a prime and let g be an element of order $p-1$ in $\Bbb Z_p$. Prove that every non-zero element of $\Bbb Z_p$ can be written as a power of $g$. So i wanted to start this proof by ...
3answers
79 views

### Elementary demonstration; $p$ prime, $1 \lt a \lt p$, $\;1 \lt b \lt p \quad$ Then $p\nmid a b$

Update: Using Bill Dubuque's lemma and logic proving Euclid's lemma, we can supply an elementary proof. To get a contradiction, assume than $p \mid a b$. Let $S = \{n \in \Bbb N \, | \, p \mid nb \}$...
0answers
56 views

1answer
98 views

0answers
82 views

### Infinitude of super happy primes

Similar to happy primes, I define super happy primes by the following process: $(1)$ Find the sum of the digits raised to the power of themselves. Ex. $13$ gives sum $= 1^1 + 3^3 = 28$ $(2)$ If ...
1answer
61 views

### Is there a maximum number of consecutive sexy prime pair sums that are all divisible by $10$?

I was finding the sums of pairs of sexy primes (prime numbers that differ by 6) and noticed that there are a lot of pairs who's sum is divisible by $10$. Ex. $(7, 13)$ as $7+13=20$ and $20$ is ...
2answers
97 views

### Is there any $k$ , for which we can prove that $n^n+k$ is never prime?

Is there any positive integer $k$, such that we can prove that $n^n+k$ is not prime for any positive integer $n$ ? $$n^n+1805$$ has a prime factor not exceeding $43$ up to $n=1805$. However, for the ...
1answer
40 views

### Proof analytic of prime number theorem

In the proof of analytic prime number theorem how can i justify $\int_{m}^{m+1} \sum_{n \leq x} \Lambda (n) dx = \sum_{n \leq m} \Lambda (n)$ where $\Lambda$ is Mangoldt function
1answer
31 views

### time the pseudo random generator gonna start repeating itself

as you know the general formula for pseudo random generator is this U(n)=a*U(n−1)+b [mod z] where we have control of U(n-1)...
1answer
35 views

### Prove $(1 + \frac{3p-3}{p^2-1}) \prod_{\substack{q=3\\q\ \text{prime}}}^{l(p)}(1 + \frac{q+1}{q-1} \frac{1}{p-1})$ goes to 1 $\lim p\to\infty$

Let function $l(p)$ be defined as the largest prime number less than $p$. For example: $l(7)=5, l(11)=7, l(17)=13$. Let the function $f(p)$ be defined as follows: \begin{eqnarray*} f(p) = \left(1 + \...
0answers
25 views

### A ratio connected to the distribution of primes

According to the Prime Number Theorem, a number $n$, roughly speaking, has probability of primality $\sigma_n:=1/\ln n$. As every schoolchild learns, one can test the primality of $n$ by looking for ...
1answer
33 views

### Algebra of the law of quadratic reciprocity [closed]

I have seen some examples that use the law of quadratic reciprocity in the form $$\left(\frac{p}{q}\right)=(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}\left(\frac{q}{p}\right)$$ I ...
4answers
33 views

### The number of quadratic residues modulo p in the set ${1,2,…,p-1}$ [duplicate]

Is it always true that the number of quadratic residues modulo p of the set ${1,2,...,p-1}$ is $\frac{p-1}{2}$ implying the rest are quadratic non-residues? if so why is this so?
3answers
82 views

### Proof that for coprime $a$ and $b$, there is a prime of the form $an+b$

Suppose , $a$ and $b$ are coprime positive integers. Is there an easy way to show that $an+b$ is prime for some positive integer $n$ ? Dirichlet's theorem states that there are infinite many ...
1answer
30 views

### Existence of Limits, $P_n/P_{n+1}$ and $P_{n+1}/P_n$.

Was curious about this question, can't seem to find this on the internet, perhaps my googling skills are rustly lol Let $(P_k)_{k\geq1}$ be the sequence of prime numbers where the $k$-th term ...
2answers
42 views

### Prove that : $2k+1$ and $9k+4$ are relatively prime [closed]

Let k be an integer Prove that : $2k+1$ and $9k+4$ are relativly prime Find in terms of $k$ the greatest common divisor of $2k-1$ , $9k+4$
1answer
48 views

### Problems : equation prime numbers : $p^2+1=q^2+r^2$ [closed]

Let $p,q$ and $r$ be prime numbers 1) Find four solutions $(p,q,r)\in N^3$ for the equation: $p^2+1=q^2+r^2$ 2) Can you generalize? Justify your answer.
3answers
61 views

### Primes number $n,n+2,n+6,n+8,n+12,n+14$

Find all natural number $n$ such that all the following numbers are primes : $$n,\;\; n+2,\;\;n+6,\;\;n+8,\;\;n+12,\;\;n+14$$ are all prime numbers
0answers
231 views

### New primality test for $2m^n+1$ (where $m$ is prime)? [closed]

If $N=2.m^n+1$ (where $m$ is prime) you can prove if $N$ is prime or not by these two steps: Step (1) if $a^{2.m^{n-1}}=L \mod(N)$ (which is $L\neq1$ ) Step (2) $L^{m}=1 \mod(N)$ So N is prime. ...
0answers
58 views

### Is 29 the only prime of the form p^p+2 [duplicate]

searched for primes of the form p^p+2 but the only one I have found is 29
2answers
60 views

### Find all prime numbers $P$ such that the sum of all divisors of $P^{4}$ is complete square [closed]

Question : Find all prime number $P$ such that the sum of all divisors of $P^{4}$ is complete square I find this problems in book and I need solution or idea to approach Please help me ...
1answer
56 views

### How to prove the irrationality of a number generated by the “$6n \pm 1$ property” of primes?

Assuming that $i > 0$ and $p_1 = 5$, let $p_i$ denote an $i$-th prime. Then we can assume that the value of $b_i$ is $0$ if $p_i = 6n-1$ and the value of $b_i$ is $1$ if $p_i = 6n+1$ (where $n$ ...
2answers
92 views