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

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
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 ...
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
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 ...
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 ...
9
votes
1answer
193 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
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 ...
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
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$?
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$ ...
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
206 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 ...
1
vote
0answers
48 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 ...
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) = ...
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 ...
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} ...
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 ...
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, ...
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 ...
0
votes
1answer
44 views

An alternating sum with binomial coefficients is not a prime number

Suppose $n\geq 5$ is an odd positive integer. Prove that $${n \choose 1}-5{n \choose 2}+5^2{n \choose 3}-...+5^{n-1}{n\choose n}$$ is not a prime number. I tried expanding each to see if anything ...
4
votes
2answers
94 views

Let $p_n$ be the $n$th prime, for any integer $n$, prove that: $p_n+p_{n+1}\geq{p_{n+2}}$

I was just wondering about it. True or false, it seems a very interesting question to me. I'm also interested to see how this could be proven or disproven? Opinions are welcome as usual. Regards
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.
3
votes
0answers
216 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
11 views

Show that $f(c)=0\forall c\in GF(p),deg(f)<p\Leftrightarrow f(X)=0$; $f(X)\in GF(p)[X]$

Let $F = GF(p)$, where $p$ is a prime integer, and let $g$ be an arbitrary function from $F$ to itself. Show that there exists a polynomial $f(X) ∈ F[X]$ of degree less than $p$ satisfying the ...
2
votes
2answers
57 views

Legendre's Conjecture limit version

Legendre conjectured that there will always exist at least one prime between consecutive squares. $\pi((n+1)^2)-\pi(n^2) \geq 1$ where $\pi(x)$ is the prime counting function. As a research project ...
2
votes
1answer
251 views

Maximum number of prime sums

Zach thinks of six different positive integers, and for each pair of numbers, he adds them. This gives him $\binom{6}{2}=15$ sums. Among these sums, find the maximum number that can be prime numbers. ...
0
votes
0answers
20 views

Define binary relation $pRq$ on the set of positive odd primes. $ x^2\equiv p \mod q$.

Define the binary relation $p R q$ on the set of positive, odd primes to mean that there is an integer $x$ satisfying $0 <= x < q$ such that $x^2 \equiv p \mod q$ holds. Is $R$ an equivalence ...
1
vote
3answers
58 views

The number of ways of writing an integer as a sum of two squares

Given an integer $m=pq$, where $p,q$ are both primes such that $p\equiv 1 \pmod{4}, q\equiv 1 \pmod{4}$. It is known that $p$ can be written as a sum of two squares (of positive integers) in a unique ...
44
votes
12answers
6k views

Proof that every number ≥ $8$ can be represented by a sum of fives and threes.

Can you check if my proof is right? Theorem. $\forall x\geq8, x$ can be represented by $5a + 3b$ where $a,b \in \mathbb{N}$. Base case(s): $x=8 = 3\cdot1 + 5\cdot1 \quad \checkmark\\ x=9 = 3\cdot3 ...
3
votes
2answers
44 views

Find the smallest prime positive integer in each of the following.

Find the smallest positive integer such that $80-n$ and $80+n$ are prime numbers. Find the smallest positive prime number such that $2002-n$ and $2002+n$ are prime numbers. I cannot ...
1
vote
0answers
50 views

Goldbach conjecture question [duplicate]

I was looking around the web and I found this question about a conjecture similar to the Goldbach conjecture. My question is: if this turns out to be true (which I highly doubt) would it be a proof ...
9
votes
3answers
797 views

Can every even integer greater than four be written as a sum of two twin primes?

Thinking of Goldbach conjecture I arrived at this $\mathrm{Conjecture}$: Every even integer greater than four can be written as a sum of two twin primes. What do you think? I hope this is ...
1
vote
0answers
27 views

Question on Newman's proof of the Prime Number Theorem

I am reading through Zagier's exposition of Newman's proof of the prime number theorem and I do not understand one of his arguments when proving his so called Analytic Theorem. This theorem states the ...
2
votes
0answers
42 views

Convergence of recurrence relation involving divisors

I$\let\leq\leqslant\let\geq\geqslant$ thought up a family of sequences, recursively defined by $$a_{n+1}=\frac{d_n^ra_n+a_{d_n}}{d_n^r+1}\quad(n\geq2)$$ where $r,a_1,a_2\in\mathbb R$ are parameters ...
0
votes
1answer
38 views

Counting the number of integers less than $x$ that are relatively prime to a primorial $p\#$

Let $p \ge 5$ be a prime. Let $x \ge 20$ be an integer. Let $p\#$ be the primorial for $p$. Let $|\{ i \le x \, \wedge \gcd(i,p\#)=1\}|$ be the count of integers less than or equal to $x$ that are ...
1
vote
0answers
32 views

When looking at the mod as binary value

Look at the next value: $$617*947 = 584299$$ 617, 947 are prime values. I want to see what are all the possible solutions for the next equation, for $k=4$: $$(a\mod k)(b\mod k) = 584299\mod k$$ ...
2
votes
4answers
60 views

Relative primes

What is the number of integers between 1 and 60 that are relatively prime to 60? I know that the answer is 16, but how do I go about finding the relative primes using a quick process?