Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
13 views

How many of the sequential primeconcatenations are prime?

2 is a prime. 3 is the next prime. 23 is also a prime. 31 is a prime. 37 is the next prime. 3137 is also a prime. Can we estimate or prove how many $XY$ are prime if $X$ and $Y$ are primes nr $n$ and ...
2
votes
0answers
83 views

Show that $\sum x^p$ over primes must have a non-trivial zero.

The sum $\sum x^n$ is unbounded in $|x| \le 1$. Similarly if $p$ is prime then trivially $\sum x^p$ is also unbounded in $|x| < 1$ because all primes $> 2$ are odd so the lower bound would ...
1
vote
4answers
44 views

In diophantine $3b^2=a^2$ where $a$ and $b$ are coprime, does $3|a$?

Integers $a$ and $b$ are co-prime and $3\cdot b^2=a^2$. $3\cdot b^2=a^2$, implies $a^2$ is divisible by 3 since, $3b^2$ is divisible by 3. Is $a$ divisible by 3?
1
vote
2answers
43 views

How Wilson's theorem implies the existence of an infinitude of composite numbers of the form $n! + 1$?

This is a paragraph in David M. Burton, "elementary number theory, seventh edition: ": But I do not understand: 1- How Wilson's theorem implies the existence of an infinitude of composite numbers ...
1
vote
1answer
62 views

What do Wikipedia's statements about the twin prime conjecture really mean?

According to Wikipedia the twin prime conjecture is a special case of the first Hardy-Littlewood conjecture: $$\pi_2(n)\sim 2C_2\frac{x}{(\ln x)^2} \sim 2C_2\int_2^n\frac{dt}{(\ln t)^2}$$ where $C_2$ ...
-4
votes
1answer
65 views

New way of finding primes - Can it be proven wrong?

So, I believe I may have discovered a new way for finding primes, but I'm not sure if there is a definite proof; If not, then I have just created my own one. Anyway, this new method I've come up with ...
1
vote
0answers
34 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 ...
2
votes
0answers
62 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 ...
0
votes
0answers
26 views

Modulo division by a prime [on hold]

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

A Complete Proof of the Fundamental Theorem of Arithmetic?

UPDATE I posted an answer but it appears I have a ways to go. In this update to my question I changed the title from $\quad$ A Simple Proof of the FTA using only elementary theory? to the one ...
0
votes
1answer
57 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 ...
-1
votes
0answers
31 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 ...
1
vote
2answers
43 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 ...
3
votes
1answer
54 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$ ...
0
votes
2answers
47 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 ...
2
votes
1answer
33 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 ...
1
vote
0answers
73 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.
6
votes
5answers
292 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 ...
1
vote
1answer
39 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 ...
1
vote
3answers
80 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 \}$...
0
votes
0answers
56 views

turning $2x$ into a perfect even

So I am trying to generate a sequence with an equation (that I don't think exists) and it involves all the even numbers, and one way to find the sequence is to get rid of all odd prime numbers so... $...
2
votes
1answer
37 views

About all primes $p$ such that $s_p=1+\prod_{k\leq p,k\text{ prime}}k$ is prime

Inspired by Euclid's proof that there are infinitely many prime numbers, I started looking at numbers of the form $$s_p=1+\prod_{k\leq p,k\text{ prime}}k$$ where $p$ is a prime number. I couldn't find ...
0
votes
2answers
47 views

Sum of factors of odd numbers

Would I be justified in saying that a number $N$, that is the product of the first $k$ odd primes, would have the largest sum of factors than all odd numbers less than $N$? ex. if $k = 4; N = 3 \cdot ...
1
vote
1answer
100 views

There cannot be more than three primes of the form $n^{n^2}-k$ for the same $k$?

I was searching for primes of the form $n^{n^2}-k$ on PARI/GP and noticed that primes of this form for same $k$ are quite rare. The probability of finding a prime of this form is $\frac {1}{n^2 \log (...
1
vote
2answers
46 views

Count number of roots of polynomial modulo prime power

I found this problem in a number theory course, I am assuming (but not sure) it is supposed to be an application of Hensel's lemma. For every $n \in \mathbb{N}_0$, determine the number of solutions ...
0
votes
0answers
167 views

Does no prime exist of the form of $k^k+11$? [on hold]

I tried searching for primes of the form $k^k+11$ on PARI/GP and found that no such prime exists for $k \le 10^4$. Questions: $(1)$ Is there any reason I cannot find a prime of the form $k^k+11$? ...
0
votes
0answers
70 views

Plotting points of the form $(-p \mod(n),0)$ and $(p,0)$

Imagine taking an interval $[-n,n]$ of the $x$-axis, cutting it in half at $x=0,$ and gluing the sides over top of each other. This process is equivalent to thinking about points of the form: $(-x \...
2
votes
1answer
108 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 ...
5
votes
1answer
62 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 ...
6
votes
2answers
98 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 ...
2
votes
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
1
vote
1answer
32 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)...
1
vote
1answer
37 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 + \...
2
votes
0answers
108 views

Is $6379$ the only prime $p \gt 2$ where $(p+1)!+1$ is prime? [closed]

I searched for primes of the form $(p+1)!+1$, where p is prime for a range of $2\lt p \le10^4$ on PARI/GP and found that $p=6379$ is the only prime in this range. Questions: $(1)$ Is $6379$ the ...
1
vote
0answers
26 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 ...
-1
votes
1answer
34 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 ...
1
vote
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?
1
vote
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 ...
0
votes
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 ...
0
votes
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$
0
votes
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.
1
vote
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
-1
votes
0answers
233 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. ...
-4
votes
0answers
59 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
-3
votes
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 ...
3
votes
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$ ...
6
votes
2answers
92 views

Prove that the number $3^{3^n} + 1$ has at least $2n + 1$ prime factors.

For any natural $n,$ prove that $3^{3^n} + 1$ has at least $2n + 1$ prime factors. My idea was to use induction: for $n = 1$: $$f(1) = 3^3 + 1 = 28 = 7*2^2$$ let it be true for $n = k$, then for $n =...
0
votes
1answer
68 views

Is there a specific theorem or name for this particular fact about primes? (Mod 6)

Is there a particular theorem or name defining the property/behavior of primes such that all primes (greater than 3) are congruent to 1 or 5 (mod 6)? I could have sworn I saw one years ago, but I ...
1
vote
0answers
46 views

Proof that the merit of a prime gap can become arbitary large?

If $p_n$ denotes the $n$-th prime number, we can define $$g_n:=p_{n+1}-p_n$$ as the gap after the $n$-th prime number. The merit of a prime gap is defined as $$m(p_n):=\frac{g_n}{\ln(p_n)}$$ It is ...
1
vote
1answer
50 views

Proof that $gcd(n, p-1) > 1$

Let $F(n) = \underbrace{111..11}_{n \text{times}}$ Proof that if $p|F(n)$ then $gcd(n, p-1) > 1$ (p - prime and $p>3$) My approach If $n$ is even it is true because $p-1$ is even too so $$...