Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

1
vote
0answers
70 views

Euclid's theorem: Paul Erdős's proof on the infinitude of primes

Seemingly simple question: Quote from Wikipedia: First note that every integer $n$ can be uniquely written as $rs^2$ where $r$ is square-free, or not divisible by any square numbers (let ...
3
votes
1answer
90 views

Under what operation prime numbers form a group?

After taking Modern Algebra I, I was wondering to find a group property among primes. It doesn't make sense. Does it? Anyways here is my first instance For any $p,q\in \mathscr{P}(prime)$ define ...
0
votes
2answers
37 views

How to decide the randomness of a dataset by checking the prime numbers inside it?

So it is weekend! I am reading currently a book where I found this sentence: "71 percent of men said they had a 'good sense of direction'. Only 47 percent of women reported same thing.", and I thought ...
1
vote
0answers
27 views

Maier's theorem

I have some questions with Maier's theorem https://en.wikipedia.org/wiki/Maier%27s_theorem If $1 < \lambda < 2$, then what? If $x+(\log x)^\lambda = x^{1+1/\pi(x)}$, then what? In particular, ...
-1
votes
2answers
59 views

Need a starter hint on python program. How do I start? [closed]

Write a program that inputs a whole number N and outputs the percentage of relatively prime pairs of numbers a, b in the range 1 to N. Can I use Euler's totient function?
8
votes
4answers
955 views

What exactly am I being asked in this question? I don't need the answer, just the interpretation.

Write a program that inputs a whole number N and outputs the percentage of relatively prime pairs of numbers a, b in the range 1 to N. For some reason, I'm having difficulty understanding the ...
1
vote
0answers
187 views

$\pi(z)-\omega(z-1)-\{-1,0,1\}= \pi(2z-1)- \pi(z)$ when $z(z-1)$ is divisible by all primes ${<}\sqrt{z}$

I have encountered the below problem: Given $z(z-1)$ divisible by all primes ${<}\sqrt{z}$ (and the prime factors of $z(z-1)$ are consecutive primes), prove (or disprove) ...
3
votes
2answers
55 views

Find prime numbers $p,q$ such that: $pq| p^p+q^q+1$

Le $p,q$ be prime numbers such that: $pq| p^p+q^q+1$ Find $p,q$ I don't have any ideas about this problem :( Thanks :)
0
votes
0answers
44 views

Prime pairs $(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$. Is there a definition about them?

I am studying congruences and I have observed this kind of prime pairs $(p,q)$ related to odd numbers. Do this kind of prime pairs have a name or have been studied before? Here is the definition: ...
0
votes
0answers
27 views

Comparing a primorial $p\#$ to Dusart's upper bound for the $n$th prime

The number of elements of a reduced residue system modulo a primorial $p$ is $\varphi(p\#)$ I thought that it would be interesting to compare each primorial $p_i\#$ to the Dusart's estimate for the ...
0
votes
1answer
39 views

improved segmented sieve of erastothenes complexity

I improved the segmented sieve of erastothenes , my algorithm doesnt repeat the multiples of primes using the equation $p^{2}_{n}p_{j}+2p_{n}p_{j} \times c =N$ wich shows when at least two multiples ...
3
votes
1answer
35 views

What is the best estimate known for the upper bound for the difference between consecutive primes?

Bertrand's Postulate gives us that: $$p_n < p_{n+1} < 2p_n$$ So that: $$p_{n+1} - p_n < p_n$$ In this answer, this paper is cited which says in Prop 6.8 that: For $x \ge 396738$ ...
10
votes
2answers
1k views

Who discovered the first explicit formula for the n-th prime?

I just found out on Wolfram that there is a formula for the n-th prime in terms of elementary functions. I wonder who found it and if he was rewarded for this. The formula (here) is: Also shown at ...
0
votes
1answer
30 views

Interesting pattern arises when plotting prime numbers on a Cartesian plane

While plotting prime numbers out of boredom one day, I stumbled upon an interesting pattern which may be expressed as such: Let $\mathbb{N}$ be the set of natural numbers. Let $\mathbb{P}$ be the set ...
4
votes
0answers
32 views

Relationship between Mersenne Primes and Triangular / Perfect Numbers

I'm a new user and have only a college sophomore's understanding of mathematics, so please bear with me. I was reading a book titled “The Simpsons and their Mathematical Secrets” in which the author ...
2
votes
1answer
72 views

Fifth root of an even number

Assume $x>1$ is an even integer, show that. $$\sqrt[5]{x} \notin \mathbb{N}$$ I am not sure if this is actually a true theorem, I am conjecturing based on $2, 4, 6, 8, 10, .... 126$. I am ...
0
votes
0answers
77 views

Carmichael function and primitive roots of unity

I have been reading about the Carmichael function recently and I would like to ask about some elementary implication of its properties as I haven't found it stated explicitly. If I understand it ...
2
votes
0answers
62 views

Is there a strong version of twin prime conjecture?

The twin prime conjecture states that : There exists infinitely many integers such that $n$ and $n+2$ are both primes for a fixed $k$, can we find integers $a_1,a_2,\cdots, a_k$ such that: ...
1
vote
1answer
42 views

What is a good example of an algorithm that is hard to parallelise?

When I have 10 computers, the factorization of a number doesn't scale along. I am not sure how much faster it would go compared to a single computer, but not 10 times faster like one would expect. ...
2
votes
0answers
167 views

Primality Test for $N=2\cdot 3^n-1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=2\cdot 3^n-1$ such ...
5
votes
5answers
70 views

If $p$ is a prime integer, prove that $p$ is a divisor of $\binom p i$ for $0 < i < p$

I was thinking of using the definition for combinations and use the fact that $p$ appears in the expansion of $\binom pi$ and hence $p$ is a divisor. I don't know whether I am on the right track!
-2
votes
1answer
97 views

Is the p'th root of a prime number p times p always prime in $\mathbb{N}$? [closed]

I've been thinking about this problem for very long: Is the p'th root of a prime number p times p(if it is in $\mathbb{N}$) always prime in $\mathbb{N}$?
4
votes
1answer
68 views

Sum and Product Puzzle and Prime Factors

Suppose we have two number $X$ and $Y,$ such that $1 < X < Y < 100,$ and $X + Y ≤ 100.$ Sue is given $S = X + Y$ and Pete is given $P = XY.$ They then have the following conversation: ...
3
votes
1answer
40 views

Prove that $\langle S\rangle$ $= G$, with $S \subset G$ and #$S > 1/p $ #$G$

I'm having trouble with solving this problem: Let $G$ be a finite group of order $> 1$, and $S \subset G$ a subset of $G$, with #$S > 1/p $ #$G$ Where p is the smallest prime factor of the ...
6
votes
3answers
103 views

Find all prime numbers p such that both numbers $4p^2+1$ and $6p^2+1$ are prime numbers?

I tried $p$ for $2, 3$ and $5$ and they are not primes for both cases. How can I find all these prime numbers that satisfy those conditions?
4
votes
1answer
52 views

Least rational prime which is composite in $\mathbb{Z}[\alpha]$?

Sébastien Palcoux asked if there was some irrational algebraic $\alpha$ such that all rational primes are primes in $\mathbb{Z}[\alpha].$ MooS answered that there are no such $\alpha.$ This leads to a ...
1
vote
2answers
45 views

If $n-1$ is prime show it is relatively prime.

If $n$ is a natural number, and $n-1$ is prime, show that, $$\gcd(n-1, (n-2)!) = 1$$ I tried: $$= \frac{(n-2)(n-3)(n-4)...1}{(n-1)}$$ But what to do?
4
votes
1answer
52 views

Prove the following are coprime

prove that $2a+5$ and $3a+7$ are coprime this is what I've done so far, all help is appreciated :) by definition two numbers $n,m$ are coprime is their greatest common divisor $\gcd(n,m) = 1$ ...
12
votes
1answer
107 views

Is there an algebraic non-rational extension of the integers, whose set of prime elements contains the prime integers?

Let the ring $\mathbb{Z}[\alpha]$ with $\alpha$ an algebraic number. Let $P(\mathbb{Z}[\alpha])$ be the set of all the prime elements of $\mathbb{Z}[\alpha]$. Question: Is there $\alpha$ algebraic ...
2
votes
0answers
70 views

Number of solutions of arithmetic function's equation [duplicate]

Say, an equation is given below \begin{equation} 2\pi(x) - \pi(2x)=\omega(x) \end{equation} where $x$ is a positive integer, $\pi(x)$ is the prime-counting function, and $\omega(x)$ is the number of ...
6
votes
4answers
86 views

Example for $\dfrac{p_1p_2-1}{p_1+p_2}$ being odd natural number .

If $p_1,p_2$ are odd prime numbers , is it possible that $\dfrac{p_1p_2-1}{p_1+p_2}$ is odd natural number greater than 1.
2
votes
0answers
37 views

Prove that $E_0$ is transcendental

Consider the non-negative natural numbers: $0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19\dots$ Encode the primes as $1$, the rest as $0$. $E = 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1\dots$ ...
13
votes
4answers
1k views

Is there a sequence of 5 consecutive positive integers such that none are square free?

Is there a sequence of 5 consecutive positive integers such that none are square free? A number is square free if there is no prime number p such that $p^2 \mid n$ What I've tried doing so far is to ...
0
votes
1answer
18 views

consecutive primes [duplicate]

Let $n\in\mathbb N$. Prove that there are $n$ consecutive natural numbers that are not prime. I tryed to use the fact about the factorization to product of primes and that there are infinite primes ...
3
votes
1answer
41 views

Arithmetic modulo primes task

I'm dealing with a problem here. The problem is as follows: There is a set $Z_p=\{0,1,2,3,...,p-1\}$ where $p$ is a prime. From this set we form a new set $B=\{x+x^{-1}\mid x\in Z_p\}$, where the ...
0
votes
4answers
58 views

prove that language is not regular (prime numbers)

$$\sum_{p\,\in\,\text{Prime}}(cb^*)^p + (b+c)^*cc(b+c)^*$$ Show that language is not regular. We see that there are two possibilities: $p$ (prime) blocks of $b's$ separated by $c$ or any string of ...
2
votes
1answer
152 views

At what point does the number twin prime between $n^2$ and $(n+1)^2$ stop increasing in count?

This question was so well stated by someone else that I am quoting their words here: Let $a(n)$ be the number of pairs of twin primes between $n^2$ and $(n+1)^2$. Of course, if the twin primes ...
1
vote
1answer
30 views

A conjecture about quadratic residues given $p \equiv 5 \pmod 8$ (Resolved)

Original Problem $p$ is a prime that is congruent to $5$ modulo $8$ and $a$ is a quadratic residue modulo $p$. Prove that excactly one of $x_1=a^{\frac{p+3}{8}},x_2=(2a)(4a)^{\frac{p-5}{8}}$ is the ...
0
votes
0answers
36 views

Can you find squares in this class?

For a problem I am working over, I would like to prove that numbers of the type are not squares $p(l^4+6l^2m^2-3m^4)$ where $p,l,m$ are integers an $p$ prime. I have already found various necessary ...
9
votes
1answer
190 views

Show $\sum \frac{1}{p}(-1)^{(p-1)/2}$ converges

Show that the sum $$\sum \frac{(-1)^{\frac{p-1}{2}}}{p}$$ converges, where the sum is taken over all odd primes. This problem was on an old Harvard qualifying exam. Is there a reasonably elementary ...
0
votes
1answer
25 views

Is the Euler prime of an odd perfect number a palindrome (in base $10$), or otherwise?

Let $N = {q^k}{n^2}$ be an odd perfect number given in Eulerian form (i.e., $q$ is prime with $\gcd(q,n)=1$ and $q \equiv k \equiv 1 \pmod 4$). (That is, $2N=\sigma(N)$ where $\sigma$ is the ...
1
vote
1answer
28 views

Is the Euler prime of an odd perfect number a repunit, or otherwise?

Let $N = {q^k}{n^2}$ be an odd perfect number given in Eulerian form (i.e., $q$ is prime with $\gcd(q,n)=1$ and $q \equiv k \equiv 1 \pmod 4$). (That is, $2N=\sigma(N)$ where $\sigma$ is the ...
0
votes
2answers
30 views

Suppose that $p$ and $q$ are primes, with $p<q$. If $n\equiv 1$ (mod $q)\ $ and $n\mid pq$, prove that $n=1$.

My professor asked us to prove this on the group theory class (we're now learning what Sylow theorems are). I found this question a little strange, because this seems to be a question from number ...
0
votes
0answers
34 views

Of what use is my code for finding prime numbers of a certain size?

I've developed a bit of mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is ...
11
votes
2answers
1k views

Prime Numbers: 6k-1 mod rule (New Discovery?)

I've noticed that although all primes follow the pattern of $6k - 1$ and $6k + 1$ which seems to be a somewhat known fact. However, I also noticed that all the primes of the pattern of $6k - 1$ only ...
4
votes
1answer
71 views

The next prime is as far as possible

Are there infinitely many primes $p$, such that the least prime greater than $p$ is $p' = \prod\limits_{i \leq k} p_i + 1$ where $2 = p_1 < p_2 < \cdots < p_k = p$ lists all prime below $p$?
0
votes
2answers
118 views

A relationship among the first $n+1$ primes

Consider the set $P_{n+1} = \{p_1, \dotsc, p_{n+1}\}$ of the first $n+1$ primes. Does there always exist a $p \in P_{n+1}$ and a partition $\{A, B\}$ of $P_{n+1} \setminus \{p\}$ (in other words, $A$ ...
3
votes
6answers
64 views

Common divisor of $a+b$ and $ab$. [duplicate]

If $\gcd(a,b) =1$. Why does $\gcd(a+b,ab)=1$ ? I know that if $\gcd(a,b)=1$ then there exists $u$ and $v$ where $au+bv=1$. But I can't seem to relate it to $a+b$ and $ab$.
2
votes
1answer
65 views

Find these prime numbers $p, q$?

Let $p, q$ be prime numbers such that $p = 3p_1 + 2; q = 3q_1 + 2$; $p + q + 3$ and $3p + 3q + pq + 3$ are square numbers. Find $p, q$? P.S. I don't have any ideas about this problem :( Thanks ...
0
votes
2answers
203 views

Number of solutions of arithmetic funtion's equation.

Say, an equation is given below \begin{equation} 2\pi(x) - \pi(2x)=\omega(x) \end{equation} where $x$ is a positive integer, $\pi(x)$ is the prime-counting function, and $\omega(x)$ is the number of ...