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.
11,568
questions
1
vote
1
answer
34
views
Multiplicative order of $2$ modulo $p$.
When calculating the multiplicative order of $2$ modulo a prime $p$ you often get $p-1$ or $\frac{p-1}{2}$ as a result, but there are cases where this does not hold, is there a general form for those ...
- 50
0
votes
0
answers
59
views
Is $f(x)$ worse than $\text{Li(x)}$ at counting primes?
This is the Gram series:
$$G(x)=1+\sum_{k=1}^\infty\frac{(\ln x)^k}{kk!\zeta(k+1)}$$
It is equivalent to the Riemann prime counting function: $$R(x)=\sum_{n=1}^\infty \frac{\mu(n)}{n}li(x^{1/n})$$
I ...
- 733
3
votes
2
answers
73
views
A function asymptotical equivalent with the prime counting function?
Let $p_n$ be the $n$-th prime number and $Q_a(N)$ be the number of primes of the form $p_n^2+a$ where $1\leq n\leq N$ and $a$ is positive and even. For some $a$ like $26,56$ it seems that no solutions ...
- 13.3k
7
votes
2
answers
1k
views
Longest geometric progression of primes
There are arbitrarily long arithmetic progressions of primes e.g. $5, 11, 17, 23, 29$ for a $5$-length progression, but no (infinite) arithmetic sequence of primes with common difference $d\neq 0$, as ...
- 3,528
1
vote
1
answer
50
views
Bertrands Postulate generalization
Bertrands postulate states that there's always a prime number in [N,2N] and I was thinking...
Considering that N=1*N and that (1,2) are the first prime numbers maybe this is just a particular case and ...
- 11
1
vote
0
answers
38
views
There are at most $n$ primes between $1$ and $2n$
This question originates from one of my tasks:
Choose $n+1$ whole numbers $a_1 \le a_2 \le ... \le a_{n+1}$ between $1$ and $2n$ inclusive.
Prove that among those $n+1$ number there exist 2 indexes $i$...
0
votes
0
answers
39
views
Goldbach Conjecture and Triangular Number
Goldbach conjecture states that every even number greater than 2 is sum of two prime numbers. We know that every positive integer can be represented as a sum of three triangular numbers.
Is it ...
-4
votes
0
answers
229
views
(Novel?) sieve that contains all primes. [closed]
Question
Per some individuals request I have to phrase this as a focused question for this Q&A site. So the main question is:
Is the following sieve and conclusion novel?
All prime numbers are ...
- 125
-3
votes
0
answers
30
views
question about GIMPS (Finding Mersenne Prime) on MacBook Terminal [closed]
This is about GIMPS – Great Internet Mersenne Prime Search, which some mathematicians use to find big Mersenne Prime numbers.
When I first opened the mprime folder to join GIMPS, I had all the ...
- 11
0
votes
1
answer
91
views
How to expand $x(x-1)(x-2)...(x-k)$
I got $$P(x)=1+\prod_{i=0}^{2021} (x-i)$$ and need to use Eisensteins's Criteria to solve the irreducibility of $P(x)$ but I found a problem how to elaborate the coefficient and choosing prime $p$. ...
17
votes
0
answers
218
views
+200
"Multiply everything so far, plug into polynomial" - can these always yield primes?
EDIT: I forgot how open number theory is! (I think that gets me put on mathematician probation or something.) For this question, I will accept any answer which assumes "standard conjectures" ...
- 218k
5
votes
2
answers
152
views
Periodic sequences of integers generated by $a_{n+1}=\operatorname{rad}(a_{n})+\operatorname{rad}(a_{n-1})$
Let's define the radical of the positive integer $n$ as
$$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\ p\text{ prime}}}p$$
and consider the following Fibonacci-like sequence
$$a_{n+1}=\...
- 1,806
0
votes
0
answers
17
views
Number Theory , Primes and sum of squares [duplicate]
Show that if $a^2+b^2≡0 \pmod{p}$ , with $p$ a prime number and $p≡3\pmod{4}$
Then automatically $a≡0\pmod{p}$ and $b≡0\pmod{p}$
What I have done so far,
Suppose $a^2≡0\pmod{p}$ and $b^2≡0\pmod{p}$ , ...
- 37
0
votes
0
answers
28
views
Exercise for equivalence of the Prime Number Theorem (P.N.T)
I want to recheck my proof of the exercise that the Prime Number Theorem is equivalent to $$\sum_{p\le x}\dfrac{\log p}{p}=\log x+M'+o(1).$$
The P.N.T here I mean the simplest form
$$\pi(x):=\sum_{p\...
1
vote
1
answer
49
views
Miller-Rabin primality test final decision. [closed]
I feel like this question is more about math than, programming but it will include some simple code for the Miller-Rabin test (in scheme-lisp).
...
- 11
0
votes
0
answers
29
views
Does $\{(f)：ℙ↣ℙ\}$ contain any analytic members $f$?, and if so What is the simplest such injective $f$? Are all $f$ necessarily monotonic? [duplicate]
(Above, $ℙ≔\{\text{all primes}_ℤ\}$.)
Are there any analytic functions that will give a unique prime output for every distinct prime input? Analyticity should preclude cheap reiterating upon a prime-...
- 19
-1
votes
0
answers
26
views
Question on prime element in factor ring. [closed]
Q/Prove that in $ \frac{\Bbb Z}{(8)}$, 2 is a prime element but not irreducible.
This is a textbook question and solving this question is very simple, but my problem is how 2 is in $ \frac{\Bbb Z}{(8)}...
-1
votes
0
answers
73
views
Can a Prime Number congruent to $3$ modulo $4$, when squared, be a non-trivial sum of two squares? [closed]
Problem : Can a Prime Number congruent to $3$ modulo $4$, when squared, be sum of two non-zero squares?
Examples
$11^2 = 121$ , can't be a sum of two non-zero squares
$7^2 = 49$ , can't be a sum of ...
- 37
1
vote
1
answer
68
views
PHI function to list relative primes
I am using a website called dcode to input numbers into the PHI function, and then receive an output of numbers relatively prime with my input.
The website, unfortunately, limits output to just 500 ...
- 145
0
votes
1
answer
41
views
For any constant $c>0$, $\sum\limits_{p\le n, \;p \;is\;prime} \frac{1}{\ln p}<c\frac{n}{\ln n}$ holds $\forall$ sufficiently large $n$
Is the following result correct?
For any constant $c>0$,
$$\sum\limits_{p\le n, \;p \;is\;prime} \frac{1}{\ln p}<c\frac{n}{\ln n}$$
holds $\forall$ sufficiently large $n$
If yes, can someone ...
- 11
1
vote
0
answers
59
views
Characterization of primes of the form $n^n+1$ by using number-theoretic functions
It is known that there is a unsolved problem related to primes of the form $n^n+1$ as is expained in page 160 of [1] (see also page 156, and the OEIS page related to this integer sequence A121270). In ...
- 55
0
votes
1
answer
50
views
Proving that $\frac{n^2-1}{n^2}\left(\frac{1}{p}+\frac{a}{b}\right)$, with conditions on integers $a$, $b$, $n$, and prime $p$, is never an integer
I have painstakingly proven that an object that I'll call $f_p$ has the form:
$$f_p=\frac{1}{p}+\frac{a}{b}$$
with $a,b,p\in\mathbb{N}$ and $gcd(p,b)=1$ such that $p$ is a bigger prime than all primes ...
- 166
1
vote
1
answer
42
views
Approximate chances of rolling primes on unknown-sided dice
There is a function for approximating the number of primes below a certain integer
What would be the function for determining the chances of rolling a prime number when rolling n number of d-sided ...
- 21
0
votes
0
answers
46
views
A Proof of Wilson’s Theorem (Without Using Modular Arithmetic)
Wilson’s Theorem says that any number $n$ is a prime number if, and only if, $(n−1)!+1$ is divisible by $n$. I came across this theorem and a proof for it in some obscure math textbook that I borrowed ...
1
vote
1
answer
54
views
Positive density of the set of the number $n$, for which its greatest prime divisor is greater than or equal $\sqrt{n}$
How can we use (as suggested by Tenenbaum's book on Introduction to Analytic and Probabilistic Number Theory) $$\lim_{X\rightarrow \infty}\sum_{\sqrt{X}\le p\le X}\dfrac{1}{p}=\log 2,$$
to prove that ...
3
votes
2
answers
69
views
Infinite set such that sum of elements of every finite subset is not a power of $p$
Let $p$, be a prime number, and $S$ an infinite set of positive integers, such that all numbers from $S$ are coprime with $p$.
Prove that there is an infinite subset $A\subseteq S$, such that for ...
- 850
0
votes
0
answers
22
views
Convergence of the singular series $\mathfrak{S}$
The $k$-tuple conjecture can be found here https://mathworld.wolfram.com/k-TupleConjecture.html. Instead of using $C(m_1,\dots, m_k)$ as the constant in the conjecture, I prefer to use the singular ...
- 19
0
votes
0
answers
36
views
Expressing any even natural number as a sum of primorials with coefficients
I'm having a hard time trying to solve the following problem:
Given any random even natural number, $x$, prove that it can or cannot be written as the product of some integer, $b$, times the primorial ...
- 199
0
votes
1
answer
49
views
Find two prime factors of a number so that the multiplication of factors give the original number
I have a number say N, I need to divide this number into p and q so that when I multiply p and q I would get original number back. Also, p and q should be two prime numbers.
Google search suggest to ...
- 179
1
vote
1
answer
24
views
Can the jacobi symbol be used for the statement "n is represented by some quadratic form of discriminant d iff 4n is a square mod d"
We've been using the above statement repeatedly in a number theory course, but to find all primes that are represented by a quadratic binary form of discriminant d, we've been using $$(\frac{d}{4p}) = ...
- 33
-1
votes
0
answers
82
views
Let $m$ and $n$ be positive integers such that $n^4+3n^2+4$ divides $5m^4+m^2$. Show that $m$ is a composite number.
PROBLEM
Let $m$ and $n$ be positive integers such that $n^4+3n^2+4$ divides $5m^4+m^2$. Show that $m$ is a composite number.
[A composite number is a positive integer that has at least one divisor ...
- 105
3
votes
2
answers
85
views
How could I prove / disprove that every non-zero integer can be written in the form $p-x^2$ where $p$ is a prime and $x$ is a positive integer?
Question: Can every non-zero integer be written in the following form?
$$p-x^2$$
I was thinking about if every non-zero integer could be written in the form $p-x^2$ where $p$ is a prime and $x$ is a ...
- 118
1
vote
0
answers
33
views
Are prime triplets & prime triples the same?
Prime Triplet & Prime Triple
Are they two different things?
A prime triple is three consecutive primes, such that the first and the last differ by six.
prime-triplets must have the form
$(p, p+2, ...
- 19
0
votes
0
answers
44
views
Primes with prime digits and prime sum of the digits
I don't know if this concept is already defined, I consider the number $n$ to be a perfect prime (weak) if $n$ is a prime, its digits are primes and the sum of the digits is prime. Every one digit ...
- 1
2
votes
0
answers
56
views
Showing the density of primes around $n$ is approximately $1/\ln(n)$
The following shows the density of primes around $x$ is approximately $1/\ln(x)$. The argument, although based on approximation, benefits from being simple enough for those without advanced ...
- 1,756
-2
votes
0
answers
53
views
Can any positive integer (arbitrary) be the prefix for some prime number? [duplicate]
Suppose we have an integer $n$.
Then, construct a prime integer $m (> n)$, such that $m - (m \mod 10^k) = n \cdot 10^k$ for some $k$.
-1
votes
0
answers
29
views
Primes and Modular Arithmetic [duplicate]
Let $p$ be a prime number and $s, r \in \{1, 2,..., p - 1\}$. Why $\exists_{i \in \{1, 2, ..., p-1 \}}$ $is \equiv p - r$ (mod p)?
In one of the books, it was taken for granted, but I don't understand ...
- 3
5
votes
1
answer
123
views
On primes less than a given number that do not divide it.
Given an integer $n \geq3$ we consider $S(n)$ to be the set of all primes less than $n$ that do not divide $n$.
The question is: Are there two distincts numbers $n$ and $m$ such that $S(n)=S(m)$?
...
1
vote
1
answer
117
views
23 and arithmetic progression
Starting at prime $23$,
$$
23 + 3 \cdot n \cdot(n+1)
$$
is prime for $n=1$ to $21$. Is there
a starting prime with more successes? Does this suggest that $23$ from
$n=1$ to $1000$ would have the ...
- 884
5
votes
3
answers
83
views
Prove contrapositive of a statement after proving its converse. (If $n$ is prime then $2^n-1$ is also prime)
I have been given the following problem:
Let n > 1 be a positive integer. Let P be the following statement:
If n is a prime number then $2^n - 1$ is a prime number
Write down the converse of the ...
- 117
1
vote
0
answers
43
views
Do the values of Euler's totient function form a complete sequence? [closed]
A sequence of natural numbers is said to be complete if every positive integer can be be expressed as a sum of values in the sequence using each value at most once.
If 1 followed by the prime numbers ...
- 17
2
votes
0
answers
73
views
Are there infinite many primes $\ p\ $ that cannot divide $\ 3^n+5^n+7^n\ $?
Let $\ M\ $ be the set of the prime numbers $\ p\ $ such that $\ p\nmid 3^n+5^n+7^n\ $ for every positive integer $\ n\ $ , in short the set of the prime numbers that cannot divide $\ 3^n+5^n+7^n\ $.
...
- 78.4k
3
votes
1
answer
239
views
$p$ ways to write $p$ as sum of primes
I hope this question is valid as I'm just curious.
in a tweet from AlgebraFact I read the following:
"There are 17 ways to write 17 as a sum of primes": $17, 2+2+13, 3+3+11, 3+7+7, 5+5+7, 2+...
- 784
0
votes
0
answers
78
views
How to calculate (20! * 12!) mod 2012 fast? [closed]
$(20! \cdot 12!) \mod 2012$
I calculated the answer multiplying each ${1 \cdot 2 \cdot 3\ldots n} $ with $\mod k$ one-by-one and found that the solution is $1684$. But I wonder if there is a faster ...
- 193
1
vote
1
answer
67
views
Generalization of $\gamma$ as limit involving primes
The following limit is utilized in Merten’s theorem.
$$
\gamma = \lim\limits_{n\to\infty}\left(-\log\log n - \sum_{p\text{ prime}}^n\log\left(1-\frac{1}{p}\right)\right)
$$
I’m interested in the ...
- 3,195
1
vote
1
answer
58
views
Estimating the $n^{th}$ prime $p_n$ in terms of $n$ for $n$ large
From the prime number theorem we know that for $n$ large ,
$n=\pi(p_n)\sim\frac{p_n}{\log p_n}$
$\implies \log n \sim \log(p_n)-\log\log p_n \ \ -(i)$
Now $p_n \sim n\log p_n$.
Some calculations with ...
- 708
4
votes
2
answers
64
views
Approximate LCM (Least Common Multiple) of $n$ random $k$-digit numbers
I choose $n$ different $k$-digit numbers randomly. I was wondering, roughly, what one can expect their LCM (least common multiple) to be? Preferably in Big O (or Big $\Theta$) notation. I'm particular ...
- 1,612
0
votes
0
answers
26
views
Order of $m+1$ in the multiplicative group of integers modulo $n$
I'm trying to figure out in what cases of $n$ and $m$ the following isomorphism holds.
$$
\mathbb{Z}_n^\times/\left<1+m\right>\cong\mathbb{Z}_m^\times
$$
I'm considering the restriction that $n$ ...
- 211
-1
votes
3
answers
123
views
Find all primes $a$, $b$, $c$ such that $a^2+a$, $b^2+b$, $c^2+c$ form an arithmetic progression
I am trying to find all primes $a$, $b$, $c$ such that $a^2+a$, $b^2+b$, $c^2+c$ form an arithmetic progression. I am curious, do any such primes even exist? If they do, can a formula to find all ...
- 1,026
4
votes
1
answer
40
views
Find the density of a certain subset of $\Bbb N$
I am trying to determine the density of the set
$$ S:=\{\,ap^r-p^s\mid p\text{ prime}, a,r,s\in\Bbb N, 1\le s\le r, 2\le a\le p\,\}.$$
These can also be described as numbers written in base $p$ as an ...
