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
1answer
36 views

How many number of ordered pair $(m, n)$ can be formed if $m+n=190$ and $m$ and $n$ are positive integers and coprime?

The question involves the concept of number theory Kindly provide the hints to solve the question not the entire solution I don't know how to approach these kind of problems
0
votes
0answers
8 views

Problems implementing the Meissel-Lehmer method

I'm working on an implementation of the Meissel-Lehmer method for calculating $\pi(x)$. I've figured out how to recursively compute $\phi$, but I'm having trouble with a more basic portion of the code....
3
votes
0answers
52 views

Is there a way to analytically extent $x^2+x^3+x^5+x^7+…+x^{prime(n)}+…$

Is there a way to analytically extent $x^2+x^3+x^5+x^7+...x^{prime(n)}+...$ I was wondering because I know that for $|x|$ smaller than $1$ it converges. I have been wondering for 2 years now I haven't ...
1
vote
0answers
42 views

Congruential equidistribution in infinite sets or sequences of positive integers

Let $S$ be an infinite set of positive integers, $N_S(z)$ be the number of elements of $S$ less than or equal to $z$, and let $$D_S(z, n, p)= \sum_{k\in S,k\leq z}\chi(k\equiv p\bmod{n}).$$ Here $\chi$...
32
votes
0answers
2k views

Towards a new proof of infinitude of primes ( with possible unified application to other primes of special forms whose Infinitude is unknown):

I'm trying to prove the infinitude of primes as follows: Consider the following partial sum : $$S(p)=\sum_{n=2}^p\sin^2\left(\frac{π\Gamma(n)}{2n}\right)$$ The summand is zero for non-primes greater ...
5
votes
0answers
28 views

Properties of prime sum graphs

The prime sum graph $P_n$ on the vertex set $V(P_n) = \{1,\dots, n\}$ has an edge $e = xy$ when $x+y$ is prime. It is easy to show that any such $P_n$ is bipartite (put odd numbers in one part and ...
1
vote
1answer
41 views

Can you prove that a seeming growing sequence goes to infinity?

I was given this problem from my brother he told me to prove that a sequence goes to infinity. It starts at 21. You write 21 in hereditary base 2 notation like this $2^{2^2}+2^2+1$. He told me to ...
0
votes
0answers
38 views

how to establish one to one correspondence between prime set and natural number set? [closed]

i know Fundamental theorem of arithmetic and prime-counting function $\frac{x}{ln\,x}$, but it can't help establish one to one correspondence.
2
votes
1answer
31 views

what is the probability that you get a prime number when you pick two random numbers between 0 and 1 ,a and b, and divide b by a and round up?

what is the probability that you get a prime number when you pick two random numbers between 0 and 1, a and b, and divide b by a and round up? let's say your random numbers where 0.09121=a, and 0.6163=...
1
vote
1answer
62 views

what is the probability that a prime number divides another prime plus 1?

what is the probability that a prime number divides another prime plus 1? what I do know is that for 2 it's 100% I can show this fact using a function $f(x,y):=$ the number of primes between $1$ & ...
-2
votes
1answer
58 views

Why is -1 not a prime number? [duplicate]

I understand the reason 1 is not considered to be a prime number, but what is the reasoning for -1 not being considered a prime number? It's only factors are 1 and itself, -1, wouldn't that make it a ...
2
votes
2answers
32 views

Are there always prime numbers that verify these parameters?

Let $p_1$, $p_2$, $p_3$, $p_4$ be prime numbers such that : $p_k\ne 2$ or $3$ for $k=1$ or $4$ $p_1\gt p_3$, $ p_4\gt p_2$ $p_1 - p_3 +2=- p_2+p_4$ Prove that for any $p_1$ and $p_2$, they exist a $...
5
votes
5answers
125 views

No solutions of $x^n+y^n=z^n$ such that $x$, $y$, $z$ are primes

Problem. Show that for $n\ge 2$ there are no solution $$x^n+y^n=z^n$$ such that $x$, $y$, $z$ are prime numbers. Personally I'd consider this a relatively cute problem which can be given to students ...
0
votes
1answer
50 views

What information about the factors of a big number can be gained in a couple of minutes?

Given a number with some hundreds of decimal figures, it's possible to check if it is a prime number if there are small factors if there are factors close to the square root. But what else? Are ...
-2
votes
0answers
80 views

Alternative sieve approach for finding prime [closed]

An alternative sieve approach for finding primes greater than $5$ is as follows: we write the numbers $-1\bmod6$ greater than $5$ ...
1
vote
1answer
56 views

Is $2^{2^m-2}+1$ always a composite number for $m>2$?

Is $2^{2^m-2}+1$ always a composite number for $m>2$ ? I really don't have any idea how to prove or disprove this , it is given to me that it is true . Since nothing else is coming to my mind , I ...
4
votes
1answer
130 views

Find prime pairs satisfying this equation

$\textbf{Question:}$Find all pairs $(p, q)$ of $\textbf{prime numbers}$ satisfying $ p^3+7q=q^9+5p^2+18p.$ $\textbf{My progress:}$ I assumed first that $p,q$ are both greater than $7$ for simplicity. ...
11
votes
1answer
389 views

Elementary proof for infinitude of primes in an arithmetic progression of a special form

In this recent question the asker was looking for a proof of the existence of infinitely many prime numbers $p$ such that both $p-2$ and $p+2$ are composite. A highly upvoted answer by Ege Erdil made ...
0
votes
1answer
26 views

Proving that there's at least two congruent modulo p numbers

I'm trying to prove the following lemma: Let p be an odd prime, and $r_1, r_2,...,r_{p-1}$ are the numbers $1,2,...,p-1$ in some order. Prove that in the series $1\cdot r_1, 2\cdot r_2,..., (p-1)\cdot ...
2
votes
0answers
37 views

Understanding principles in integer sequence

I am an engineering student and when I was doing some work on data visualisation I stumbled across an integer sequence after watching a video about sequences that produce interesting graphs. I ...
12
votes
3answers
3k views

How does $\cos(2\pi/257)$ look like in real radicals?

We know $\cos(2\pi/p)$ for p a Fermat prime can be expressed in real radicals. The case $p=17$ is a root of an 8th deg eqn, but can be also given as a sequence of nested radicals, $$\begin{aligned} 4\...
1
vote
0answers
27 views

Prove that $7$ is a primitive root modulo $p=2^s+1$. [duplicate]

I need help with the following question: If $1<s\in \mathbb N$ and $p=2^s+1$ is prime, so $7$ is a primitive root modulo $p$. My thoughts: First I know: $\phi(p)=p-1=2^s$. So if $r$ is the order ...
4
votes
1answer
69 views

Existence of a prime in $(\phi(n), n]$

The question is: for any $n\geq2$, is there always a prime $p$ satifying $\varphi(n)<p\leq n$? Here $\varphi(n)$ is the Euler totient function. We know that there is always a prime between $n-O(n^\...
0
votes
2answers
50 views

Efficiently computing $\sum_{\sqrt{N} \lt p \in primes \leq N} \lfloor \frac{N}{p} \rfloor$

I'm interested in computing $f(N) = \sum_{\sqrt{N} \lt p \in primes \leq N} \lfloor \frac{N}{p} \rfloor$ $N$ is large enough that primes up to $\sqrt{N}$ are available, but not much beyond and ...
0
votes
1answer
36 views

Question about proof of 'There are infinitely many primes $p$ with $p \equiv 2(\text{mod3})$'

I have read other proof, but I am stuck on the proof in my algebra class. Hope someone could help me. Thanks a lot. Prove by contradiction. Let $ \{ p_1,\dots p_n\} $ be our finite primes with $p_i \...
1
vote
0answers
30 views

Sum of all subsets of the set of even coprime integers relative to a power of a prime

Let $p$ be an odd prime and $k\in \mathbb{N}$. Let $S$ be the set of even coprime integers relative to $p^k$, i.e. $$S=\{2,4,\ldots,2\frac{p^k-1}{2}\}\setminus\{2p,\ldots,2p\frac{p^{k-1}-1}{2}\}.$$ ...
47
votes
6answers
8k views

I'm trying to find the longest consecutive set of composite numbers

Hello and I'm quite new to Math SE. I am trying to find the largest consecutive sequence of composite numbers. The largest I know is: $$90, 91, 92, 93, 94, 95, 96$$ I can't make this series any ...
0
votes
1answer
25 views

Field theory: prove that $(\forall x \in \mathbb{F}_p : f(x) = g(x)) \iff f - g \in \mathbb{F}_p[X](X^p - X)$.

Let $p$ be a prime and $f, g \in \mathbb{F}_p [X]$. Prove: $(\forall x \in \mathbb{F}_p : f(x) = g(x)) \iff f - g \in \mathbb{F}_p[X](X^p - X)$. I have proved the implication ($\implies$). However, ...
2
votes
2answers
163 views

Number Theory: If $d\mid(4^n+1)$, show that $d$ is a sum of two squares

I have a proof for the following problem, but I'm not sure if it's correct: If $d\mid(4^n+1)$, show that $d$ is a sum of two squares. Proof $d\mid(4^n+1)\implies dm=4^n+1$, some $m\in\mathbb{Z}$. ...
99
votes
0answers
2k views
+100

Sorting of prime gaps

Let $g_i $ be the $i^{th}$ prime gap $p_{i+1}-p_i.$ If we re-arrange the sequence $ (g_{n,i})_{i=1}^n$ so that for any finite $n$ the gaps are arranged from smallest to largest we have a new sequence ...
3
votes
0answers
48 views

Would a finite number of primes imply there would be a finite number of secure exchanges on the internet?

I was teaching my class Euclid's theorem on why there are infinite number of primes. Aside from the idea of proof by contradiction, I wanted to give some more motivation as to why knowing this fact is ...
7
votes
0answers
102 views

When is $p^{p-1}+p-1$ prime for a prime number $p$? [closed]

Let $p$ be a prime number. Then $p^{p-1}+p-1$ is prime when $p=2,3,31$. My question is whether the number of such primes is finite or not.
1
vote
1answer
55 views

Prime number lists

"Find the smallest possible integer n with the property that there exists a prime $p$ such that the $6$ numbers: $p, p+n, p+2n, p+3n, p+4n, p+5n$ are all prime numbers." Okay, so I have ...
-1
votes
0answers
89 views

Can anyone help me verify if this prime sieve is going to work ? Also, can anyone help me determine whether this has high computational efficiency?

Here's a link to my conjecture : Quora - My New Prime Number Sieve Here's the content: A New Prime Sieve ! Hello there ! I think I’ve found a way to find prime numbers ! (Not a function, but a ...
17
votes
3answers
2k views

Proof of Infinitude of Primes by Euler's Product Formula is Circular?

Many guides will refer to Euler's product formula as simple way to prove that the number of primes is infinite. $$\sum_n\frac{1}{n} = \prod_p \frac{1}{1-\frac{1}{p}}$$ The argument is that if the ...
3
votes
1answer
85 views

Proving The Irreducibility Of $X^{2p}+pX^n-1$ Over $\mathbb{Z}[X]$

The following is an exercise in Victor V. Prasolov's Polynomials (Second edition, Page no. $74$, exercise $2.10$) Problem: Let $p>3$ be a prime and $n<2p$ a natural number. Prove that $$P(X)=X^{...
2
votes
1answer
157 views

On the inequality $\left(\frac{R_{n+1}}{R_n}\right)^n<n^{\frac{5}{4}}(\log n)^3$ for Ramanujan primes

The Wikipedia Firoozbakht's conjecture refers (see also the comments of OEIS A182514) an inequality due to Nicholson, I wondered if it is possible to prove the following conjecture. Conjecture. The ...
2
votes
3answers
84 views

Prime number logic

It is conjectured that for every intever $n\geq1$ there is a prime $p$ with $n^2<p<(n+1)^2$. Show that if this conjecture is true then $\pi(x)\geq\lfloor\sqrt{x}\rfloor$ for all $x\geq2$. I ...
1
vote
1answer
28 views

Counting consecutive integers that are divisible by primes relatively prime to an arbitrary $n$

Let: $c > 0, n, m, x > 0$ be an integers $p\#$ be the primorial of $p$ $D_n(m,x)$ be the count of integers $i$ where: $m-x \le i < m$ There exists a prime $p$ that $p \nmid n$ but $p | i$ ...
0
votes
1answer
63 views

Factorial modulo a larger prime

$\textbf{Question:}$If $n$ is an integer and $p$ a prime larger than $n+1$, are there any conditions we can put on $n$ so that $n! \equiv -1 \pmod{p}$
3
votes
0answers
28 views

Existence of primes less than double a previous prime (two steps back) - extending Bertrand?

Say we have three sequential primes: $p_1, p_2, p_3$ I know by Bertrand's postulate that $p_2<2p_1$ However, what I wonder is for $p_1>7$ if the following is always true: $p_3<2p_1$ A ...
3
votes
1answer
123 views

Relationship between primes, right triangles and homogeneous polynomials

It is known that if $x^2 + y^2 = z^2$ is a primitive Pythagorean triplet then $z$ is not divisible by any prime of the form $4k-1$. The following is a generalization of this classical result which ...
3
votes
2answers
85 views

Reasoning about relatively prime factors of consecutive integers

Let: $n,m,x$ be any integer with $n$ being even $D_n(m,x)$ be the count of integers $i$ where: $m-x \le i < m$ There exists a prime $p \le x$ such that $p \nmid n$ but $p | i$ Examples: $D_6(0,5)...
4
votes
0answers
163 views

Asymptotic formula for Prime Numbers

My question is: Obtain an asymptotic estimate for the sum $$S(x)=\sum_{x<p \leq 2 x} \frac{1}{p}$$ with relative error $1 / \log x$ (i.e., an estimate of the form $$S(x)=f(x)(1+O(1 / \log x))$$ ...
1
vote
1answer
42 views

Shift Modulo Operation

Shift Modulo Operation Let positive integer $m$ be a base and function $f(x,m)$ is defined over positive integers $x,m$ such that $f(x, m) = x$, if $x < m$ $f(x, m) = f( \lfloor x/m \rfloor + x \...
6
votes
4answers
716 views

Infinite prime proof using factorial plus one or product of primes plus one?

My instructor provided a proof for the Theorem: The number of primes is infinite.Proof by ContradictionAssume finite number of primes this means there is a largest prime say $p$.Now lets say there is ...
5
votes
1answer
49 views

Using elementary methods to prove infinitely many primes mod n

I was reading an elementary number theory text looking to enhance my knowledge and I came across the relatively simple task of proving there existed infinitely many primes of the form $4k-1$ (of ...
0
votes
1answer
26 views

How many numbers between 1 and 1,000 (both inclusive) are divisible by at least one of the prime between 1 to 50? How can I find this? [closed]

I was trying to solve a compettive programming problem in which constraints are so high so I want to deduce a formula for it so that i could do it for other ranges as well.
6
votes
1answer
158 views

Infinitely many common prime divisors

By Zsigmondy's theorem, there are infinitely many prime divisors of $2^{2^n}-1$. That is, the set $$A=\{p \text{ is a prime}: p\mid 2^{2^n}-1 \text{ for some }n\in\Bbb{N}\}$$ is infinite. Also, as ...
0
votes
1answer
59 views

The equation $y^2=x\pm \ell $

For what odd primes $\ell$ does the equations $y^2=x\pm \ell$ have a finite set of solutions over the integers. Here, assume $y$ is even and $x$ is a prime number. I am not sure if this is really ...

1
2 3 4 5
203