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.

learn more… | top users | synonyms

3
votes
1answer
140 views

N+1 Primality Proving is slow

I am trying to implement the N+1 method of proving primality. Here is my description, based on the Brillhart, Lehmer, Selfridge paper, Theorem 13 and Corollary 8: Choose P and Q such that D = P^2 ...
-1
votes
1answer
269 views

Integer linear combinations of coprime integers

Consider the finite set $S=\{s_1,s_2,\dots,s_n\}$ such that $GCF(s_1,s_2,\dots,s_n)=1$. Show that $\exists n$ such that $n$ cannot be written as $n=c_1s_1+c_2s_2+\dots+c_ns_n \forall c_i,s_i \in ...
7
votes
2answers
188 views

Do we know a number $n\gt 5$ with no twin prime $n\lt q\lt 2n$?

This is essentially a Bertrand's postulate version for twin primes. I am interested in both an explicit example and large lower bounds for it because of this answer of mine. In the comments below the ...
7
votes
1answer
136 views

Are there more numbers in this integer sequence? 3, 8, 12, 24

I was using some low primes for RSA encryption today, and noticed that for $p=5$, $q=7$, and ANY valid encryption key value, encrypt(encrypt(message)) = message. I thought this was an interesting ...
3
votes
2answers
107 views

Does factorization end with a prime number?

When doing factorization, I have always taught kids to work from the outside in. So for the number $28$, you start with $1$ and $28$, then $2$ and $14$, then $4$ and $7$. And once you reach the ...
0
votes
1answer
158 views

For all $n$, $9^n + 25^n - 1$ has a prime factor with $7$ in its decimal representation?

Let $x_n$ be a sequence of positive integers defined by $x_n=9^n + 25^n -1$ for all $n \ge 2$ I conjectured that there exists at least one prime divisor of $x_n$ which contains $7 $ in its decimal ...
1
vote
0answers
122 views

About $f(s)=\sum_{a^2+b^2>0} \frac{(-1)^{a^2+b^2}}{(a^2+b^2)^s}=0$ and the Extended Riemann Hypothesis.

Let $s$ be a complex number with a strictly positive real part ($Re(s)>0$). Let $f(s)=\sum_{a^2+b^2>0} \dfrac{(-1)^{a^2+b^2}}{(a^2+b^2)^s}$ where the sum runs over all positive integers $a,b$ ...
4
votes
1answer
112 views

Carmichael Number

I am little bit confused with the definition of Carmichael Number Wikipedia(http://en.wikipedia.org/wiki/Carmichael_number) saying that Carmichael Number is a composite number satisfies ...
12
votes
2answers
2k views

Elementary proof of Zsigmondy's theorem

I've been writing a not-so-short introduction to elementary number theory, supplying proofs for all theorems. When coming across Zsigmondy's theorem, it seemed difficult to find a proof available on ...
2
votes
2answers
551 views

Prime number test and Fermat's little theorem

We've learn in class that if $a^{p-1} \not\equiv 1 \pmod p$ then $p$ must be a composite number. What is the explanation for that? Thanks!
1
vote
0answers
132 views

The maximum distance between two successive coprimes of n

I am exploring the symmetries and distribution of the coprimes of a natural number $n$. Does anyone have any insight into how to express the maximum distance between two successive coprimes of $n$? ...
5
votes
1answer
224 views

Proving that e.g. 421 is prime in a formal system

I'm working in the formal system Metamath, and in the course of learning about number theory I've become acquainted with theorems, such as Bertrand's postulate, that require hand-calculation that a ...
0
votes
2answers
65 views

Prove that $a^2 \equiv b^2 \pmod q$ if and only if $a\equiv\pm b \pmod q$ for any prime numbers $q$.

Prove that $a^2 \equiv b^2 \pmod q$ if and only if $a\equiv\pm b \pmod q$ for any prime numbers $q$ homework question, please help.
1
vote
2answers
198 views

Prime factorization: easiest way?

For prime factorization, is there another way of doing it, distinct from dividing the number by a series of primes (starting by the smallest)? Couldn't we also pick the same series of primes and ...
5
votes
0answers
125 views

Are $ut + 1$ and $ut + t + 1$ both prime for some t for any $u$?

Conjecture : For any natural number $u$, there is a natural number $t$ such that $ut + 1$ and $ut + t + 1$ are both prime. So we get a solution of the equation $$au - b(u+1) = -1$$ with prime ...
2
votes
4answers
236 views

Relatively prime integers proof

I am asked to prove that: For integers $n, x,y > 0$, where $x,y$ are relatively prime, every $n \ge (x-1) (y-1)$ can be expressed as $xa + yb$, for $a,b \ge0$. How should I approach ...
21
votes
2answers
583 views

How to either prove or disprove if it is possible to arrange a series of numbers such the sum of any two adjacent number adds up to a prime number

I'm wondering if it's possible to write a theorem to prove or disprove the possibility of arranging a sequence of numbers (1,2,...n) such that the sum of any two numbers adds up to a prime number. An ...
0
votes
1answer
69 views

Greatest possible number of primes between 1 and $x$

Background: I'm making a program in java to calculate all the primes between 1 and any given number ($\pi(x)$). I want to create an array that will contain all the numbers, but resizing an array takes ...
1
vote
3answers
78 views

Can prime quadruplets be adjacent

Can prime decade's ( 101, 103, 107, 109 ) be adjacent? And if not, why not? I.e.: ...
5
votes
1answer
187 views

what should I do if i've find a larger prime number than the largest

I've found a prime number larger than the known largest prime number; it has 21,785,121 digits. Who should I contact for the award (if there is one)? Thanks.
1
vote
0answers
90 views

Does the Riemann zeta function tell us about the order theoretic properties of the natural numbers?

The classical Möbius function $\mu(n)$ fulfills the multiplicative inversion formula, e.g. see this thread. Now I see in the theory of posets, they generalize the concept of that function, see ...
2
votes
2answers
63 views

Weak versions of Bertrand's postulate

We are interested in the following statement: For each $n>1$ and $x>2$ there is at least one prime $p$ satisfying $x<p<n x$. For $n=2$ we get precisely the Bertrand's postulate which is ...
0
votes
1answer
116 views

do you know another Magic Square with this property?

with the repeating digits of $\frac{1}{19} = 0.052631578947368421$ we can construct an exceptional magic square : The number 19 is a cyclic number with a period of 18 before the digits start to ...
5
votes
2answers
157 views

Show that $-3$ is a primitive root modulo $p=2q+1$

This was a question from an exam: Let $q \ge 5$ be a prime number and assume that $p=2q+1$ is also prime. Prove that $-3$ is a primitive root in $\mathbb{Z}_p$. I guess the solution goes ...
2
votes
2answers
1k views

Finding a least common multiple (LCM)

My Algebra 2 book explains how to find a least common multiple: Find the least common multiple of $4x^2 - 16$ and $6x^2 - 24x + 24$. Solution Step 1 Factor each polynomial. Write ...
0
votes
1answer
44 views

Summation of a curious series-repeated division by primes

I am interested in knowing if there is some closed form/formula for the following series: ...
0
votes
1answer
60 views

Interesting inequality using primorial

Not assuming PNT, what is $a$ in $$(p\#_x)^a=(2^{1/2})(3^{1/3})(5^{1/5})...$$ where $p\#$ is primorial till $x$, and r.h.s is over primes. Also answer can be asymptotic !
2
votes
4answers
223 views

If $p,q,r$ are all primes,and $p|qr-1$,$q|pr-1$ and $r|pq-1$,find all possible values of $pqr$.

If $p,q,r$ are all primes,and $p|qr-1$$~~~~~~~~~~~~~$$q|pr-1$$~~~~~~~~~~$ and $~r|pq-1$. Find all possible values of $pqr$. My work: $qr-1=pk_1$ $pr-1=qk_2$ $pq-1=rk_3$ From the above equations, we ...
6
votes
2answers
578 views

Is every non-square integer a primitive root modulo some odd prime?

This question often comes in my mind when doing exercices in elementary number theory: Is every non-square integer a primitive root modulo some odd prime? This would make many exercices much ...
6
votes
2answers
337 views

Relatively prime property verification

I am reading a computer science puzzles book. And I get the following question - "You have a five quart jug, a three quart jug and unlimited supply of water. How would you come up with exactly four ...
3
votes
2answers
86 views

Let $x$ be greater than $1$. Prove $x$ is prime if and only if for every integer $y$, either $\gcd(x,y)=1$ or $x\mid y$.

I've been having serious trouble with this problem, The first direction-> Proving x is prime if for every integer y, either gcd(x,y)=1 or x|y doesn't seem too difficult. We know that if gcd(x,y)=1 ...
3
votes
1answer
105 views

Problem in elementary number theory about prime numbers.

I was looking at a packet of problems in elementary number theory, when I saw this question: Show that $n$ is prime iff ...
7
votes
1answer
324 views

Does $19,199,1999,\dotsc$ contain infinitely many prime numbers?

Are there infinitely many primes of the form $F_n =2\times10^n-1$? That is, does this sequence, $$19,199,1999,\dotsc$$ contain infinitely many prime numbers? I think about Dirichlet's theorem on ...
1
vote
2answers
83 views

Function approximating this product

Is there any function approximating, for large values of $p$, the quotient between the product of all primes and the product of all primes $-1$? Basically: $2/1 \cdot 3/2 \cdot 5/4 \cdot 7/6 \cdot ...
1
vote
0answers
36 views

Schoenfeld's limits & almost primes

If I am correct in my understanding, the Tao-Green theorem employed almost primes as density normalisers. If $N_k(x)$ is the counting function of almost primes, is the study of almost primes 'useful' ...
1
vote
3answers
116 views

Number of prime numbers in a range

Is there any function to evaluate the number of prime numbers between [2, n]? For example, consider the following range: ...
9
votes
1answer
478 views

Is the Green-Tao theorem a consequence of the Euler's theorem?

The Erdős-Turán conjecture states that If $A\subset\mathbb{N}$ is such that $$ \sum_{n\in A} \frac{1}{n} = \infty,$$ then $A$ contains arithmetic progressions of any given length. I'm ...
2
votes
2answers
1k views

Factorials and Prime Factors

I need to write a program to input a number and output it's factorial in the form: $4!=(2^3)(3^1)$ $5!=(2^3)(3^1)(5^1)$ I'm now having trouble trying to figure out how could I take a number and get ...
1
vote
1answer
266 views

Number of twisted primes less than 20,000

We call number $N$ a twisted prime if we turn all the 6-es in 9s and all the 9s in 6-es and it remains a prime(If it has no 6-es or 9s it is not twisted). How many twisted primes there are? ($N \leq ...
1
vote
3answers
107 views

$x^2-p=0$, with $p$ prime, have irrational roots.

Unaware that $\sqrt{p}$ is irrational, prove that as $x^2-p=0$ have irrational root for $p$ prime? How would you use the criterion of Eisenstein?
2
votes
0answers
122 views

Liouville function and PNT

The Big Omega function is defined as the number on non-distinct prime factors of an integer. I.e. $\Omega (2^a3^b...p^z)=a+b+...+z$, and the Liouville function is defined as ...
1
vote
3answers
98 views

Trying to understand why “long blocks between primes” must exist

I'm currently going through "An Introduction to the Theory of Numbers" by Hardy and Wright and at one point, they discuss why the distance from one prime to the next must have a long chunk of ...
0
votes
2answers
61 views

Euclidean lemma proof [duplicate]

According to Euclidean lemma it is defined that if $p$ is prime then $$p|ab\Rightarrow p|a\lor p|b$$ How to prove by descending induction that if $$p|a^n \Rightarrow p|a $$ knowing that $a^n = a ...
0
votes
2answers
49 views

Show that if a prime number $p|a^n$ then $p|a$ [duplicate]

The title says it all, how can I prove the following: Show that if a prime number $p|a^n$ then $p|a$
-1
votes
2answers
253 views

Divisibility of prime numbers

I have this exercise in my worksheet in the discrete mathematics course.I don't understand the part that deals with prime numbers in integer-divisibility. "Show that for a prime number $p$, if a ...
5
votes
1answer
321 views

On a constant defined by Ramanujan.

In the second letter to Hardy Ramanujan writes about the number of prime numbers less than $n$ there he writes. Here this constant $\mu$ facinated me . What is its closed form? and How to compute ...
1
vote
2answers
199 views

Determine a generator of $\mathbb{Z}^*_{11}$ manually.

What is the best/standard way to do this manually? Could you describe a solution in a step-by-step fashion.
6
votes
2answers
140 views

A question about LCM (number theory, supposedly high school level)

The question is: Determine whether or not there are positive integers $a, b, c$ such that: $\text{lcm}(a, b) = \text{lcm}(a + c, b + c)$. I've tried writing $\text{lcm}(x,y)$ as $xy/\text{gcd}(x,y)$, ...
18
votes
2answers
489 views

Conjecture: the sequence of sums of all consecutive primes contains an infinite number of primes

Starting from 2, the sequence of sums of all consecutive primes is: $$\begin{array}{lcl}2 &=& 2\\ 2+3 &=& 5 \\ 2+3+5 &=& 10 \\ 2+3+5+7 &=& 17 \\ ...
2
votes
2answers
107 views

Manually performing the Miller-Rabin probabilistic primality test

What is the standard/best way to do that manually? Could you give an example with $n=241$ and $a = 3$.