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.
