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
1answer
43 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. ...
1
vote
4answers
40 views

Inverse of a prime with period 5

For a certain 3-digit prime $p$, the decimal expansion of $1/p $ has period $5$. Find $p$. Approach? Thank you.
0
votes
1answer
116 views

Does Bertrand's Postulate give us the tightest proven upper bound for prime gaps?

Bertrand's Postulate asserts that there is a prime between $n$ and $2n$. Is this the best such upper bound on prime gaps known today, or have stronger estimates been proved? I mean results of the ...
1
vote
2answers
52 views

Is the Legendre sieve explicit?

The Wikipedia page for the Legendre sieve... http://en.wikipedia.org/wiki/Legendre_sieve ...says that the Legendre sieve gives upper and lower bounds on the number of primes in a given range. In ...
5
votes
5answers
71 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!
4
votes
1answer
74 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: ...
6
votes
3answers
104 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?
3
votes
1answer
41 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 ...
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 ...
3
votes
0answers
150 views

The n-envelope problem

This is original problem: You have n number of envelopes, and $100$ $\$1$ bills. you have to put these bills in the envelopes in such a way that any amount between $1$ to $100$ can be reached just ...
1
vote
0answers
49 views

Count of lower and upper primitive roots of prime $p \equiv 3 \bmod 4$

I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of $p/2$. Many primes have an exact match between ...
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$ ...
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 ...
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?
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 ...
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 ...
0
votes
2answers
119 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$ ...
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 ...
3
votes
3answers
115 views

If $p \mid m^p+n^p$ prove $p^2 \mid m^p+n^p$

Prove that for a prime $p>2$, if $p \mid m^p+n^p$, prove $p^2\mid m^p+n^p$ From Fermats theorem I concluded $p \mid m+n$, so $p^2\mid (m+n)^p$. How do I proceed next? Any hints are welcomed.
0
votes
4answers
61 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 ...
9
votes
1answer
195 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 ...
5
votes
2answers
139 views

A prime number generator algorithm based on $x^2+(x-1)^2$ that generates only primes

I think I could have found a prime number generator algorithm, but still I am not very sure, maybe this is an already known property of perfect square numbers, maybe not, but it looks amazing and I ...
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.
20
votes
2answers
355 views

The Gaussian moat problem and its extension to other rings in $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$

One of my favourite open problems in number theory, an area in which I enjoy only as a hobbyist, is the Gaussian moat problem, namely "Is it possible to walk to infinity in $\mathbb{C}$, taking ...
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$ ...
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
1answer
19 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 ...
2
votes
1answer
153 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
31 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 ...
3
votes
0answers
217 views

Question about the elements of a reduced residue system relative a primorial $p_n\#$

I've been dividing up the elements of reduced residue system relative a prime $p_n$ into congruence classes modulo $p_{n+1}$ and I noticed that each congruence class is represented. If $r$ = the ...
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 ...
1
vote
2answers
43 views

Need help with formula for generating primes

I've done this: N[Sum[(10^(n*2) + 1)/(10^(n^2*2)*(10^(n*2) - 1)), {n, 1, Floor[49^(1/2)]}], (49)*2] ...
0
votes
0answers
35 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 ...
2
votes
1answer
158 views

How to find prime numbers

I am looking for a formula that tells me what the next prime number will be. It is hard to do this without a formula because for example there is a small gap between 17 and 19 then a big one between ...
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 ...
4
votes
1answer
72 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$?
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
0answers
285 views

Prime numbers with binomial coefficients

Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$ for every $$j\in ...
2
votes
2answers
71 views

Proving if it is prime

I'm quite lost on how to prove things, with the $n \choose k$ and proving. So the question is: Prove that $n \choose k$ is divisible by $n$ if $n$ is a prime number and $1 \le k\le n-1$ Like, how ...
1
vote
1answer
24 views

Mersenne primes and superperfect numbers

Definition: Let $n\in\mathbb{Z}$ with $n>0$. Then $n$ is said to be superperfect if $\sigma(\sigma(n)) = 2n$. Where $\sigma$ is the sum of positive divisors arithmetic function. ($\sigma(n) = ...
0
votes
2answers
62 views

Fermat little theorem : show that if $p$ is prime, then $a^p \equiv a\pmod p$ holds, if $p$ divides $a$.

Fermat little theorem : show that if $p$ is prime, then $a^p \equiv a \pmod p$ holds,if $p$ divides $a$. I know it doesn't hold but I'm having a hard time proving it.. I know that if $p$ divides ...
5
votes
1answer
70 views

Prime numbers and Topology

I was doing this homework for my university in which I had to prove that the set of prime numbers was infinite, just like Harry Furstenburg did by considering the following topology: Let $\mathcal{O} ...
2
votes
0answers
37 views

Using the Dirichlet's Theorem to find the number of primes in an arithemetic progression.

Dirichlet's Theorem says that the sequence of integers {Ak+B}, where A, B have no common divisor other than +-1, contains infinitely many primes. It does not say that all such numbers Ak+B are prime, ...
31
votes
3answers
7k views

Yitang Zhang: Prime Gaps

Has anybody read Yitang Zhang's paper on prime gaps? Wired reports "$70$ million" at most, but I was wondering if the number was actually more specific. *EDIT*$^1$: Are there any experts here who ...
2
votes
4answers
48 views

Certificate of primality based on the order of a primitive root

Reading my textbook, it tells me that to prove $n$ is prime, all that is necessary is to find one of its primitive roots and verify that the order of one of these primitive roots is $n-1$. Now, why ...
34
votes
7answers
5k views

What is an odd prime?

I heard the term "odd prime" often. Isn't it redundant? If $n$ is even then $2$ divides $n$ so it's not prime. Why is "odd" emphasized?
11
votes
3answers
274 views

Finding $n$ satisfying $\{1^n-0^n,2^n-1^n,\cdots,p^n-(p-1)^n\}\equiv \{0,1,\cdots,p-1\}\pmod p$

Background : About a month ago, a friend of mine taught me his findings about a few polynomials which cover all the residue classes in mod $p$ where $p$ is a prime. Then, I began to consider the same ...