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.

1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
-1
votes
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 ...
1
vote
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 ...
3
votes
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$ ...
0
votes
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 ...
2
votes
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 ...
1
vote
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.
6
votes
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 ...
1
vote
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$ ...
1
vote
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 ...
1
vote
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 \}$...
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
46 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
98 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
165 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
67 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 \...
1
vote
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 ...
5
votes
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 ...
6
votes
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 ...
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
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)...
1
vote
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 + \...
1
vote
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 ...
-1
votes
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 ...
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
0
votes
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. ...
-4
votes
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
-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
67 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 $$...
0
votes
0answers
31 views

A prime $p$ doesn't divide $\dbinom{p^am}{p^a}$ [duplicate]

Let $p$ be a prime, and $(a,m)\in{\Bbb{N}^2}$ with $\gcd(p,m)=1$. Then $p$ doesn't divide $\dbinom{p^am}{p^a}$. I need this to prove the existence Sylow theorem. I don't really know how to proceed.
0
votes
2answers
37 views

How to calculate the probability of a large number to be divisible by a prime number?

For example, $\frac{23023}{23}=1001, \mod 0$. Let's say I want to encode my book with number $23$ as my pattern that shows the intactness of my book in any new print. I also do not declare this but ...
0
votes
2answers
52 views

Let : $A=\frac{2^{4n+2}+1}{5}$ , $n>1$

Prove that the number A is not primary Such that : $A=\frac{2^{4n+2}+1}{5}$ $n≥2$ n=2 then $A=205$ Please I need some ideas to approach it
-2
votes
1answer
66 views

Can I prove n^2 - n + 1 prime for all even n? [duplicate]

I was playing around with numbers the other day and realized that the first few values for $n(n - 1) + 1$ are prime. Now, I also quickly realized that not all values are prime ($n = 5$ results in 21, ...
0
votes
1answer
36 views

If the order of a number (mod n) equals n-1 then n is prime? [duplicate]

I have trouble in understanding the last part of the sufficiency proof of Pépin´s Test (https://en.wikipedia.org/wiki/Pépin%27s_test). "In particular, there are at least least F_{n}-1 numbers below ...
-1
votes
1answer
48 views

$p^n+1=k^3$ where $p$ is a prime and $k$ is a positive integer. [closed]

My problem: Find all the prime numbers $p$ for which there exists a positive integer $n$ such that $p^n+1$ is a cube of a positive integer.