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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$...
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
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$. ...
user avatar
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" ...
user avatar
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}=\...
user avatar
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}$ , ...
user avatar
  • 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\...
user avatar
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). ...
user avatar
  • 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-...
user avatar
-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)}...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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}) = ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$.
user avatar
-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 ...
user avatar
  • 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)$? ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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\ $. ...
user avatar
  • 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+...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
-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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
232