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

0
votes
0answers
45 views

find all primes $p$ such that $a^p-1$ has a primitive factor.

We say that a prime $q$ is a primitive factor of $a^n-1$ if $q|a^n-1$, but $q$ does not divide $a^m-1$ for any $m$ such that $0<m<n$. Given $a\ge2$, find all primes $p$ such that $a^p-1$ has a ...
0
votes
1answer
62 views

Is there a primality test based on the sum of squares of the first $n$ natural numbers $\sum_{x = 1}^{n} x^2$?

The Fibonacci and Catalan primality tests are based on the calculation of the congruences of those numbers versus the possible prime $n$ (the rules are different depending on the primality test), and ...
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?
4
votes
1answer
46 views

Upper bound for $\prod_{ 5 \leq p <n} p^{\frac{n}{p-1}}$

Does anyone know how I could get a good upper bound for the following: $$R := \prod_{\substack{ p \; \text{prime} \\ 5 \leq p < n}}p^{\frac{n}{p-1}}$$ I'm not that skilled at asymptotic analysis ...
3
votes
2answers
82 views

Why $\prod\limits_{n<p\le2n}p\le\binom{2n}{n}$

Why is for $p$ prime, $\prod\limits_{n<p\le2n}p\le\binom{2n}{n}$ I think induction doesn't work; the factor from $\prod\limits_{n-1<p\le2n-2}p\quad$ to $\prod\limits_{n<p\le2n}p$ can be ...
5
votes
1answer
65 views

Clarification of Proof involving $\sum_{p \le x} \frac{1}{p}$

For fun I've been doing problems from M. Ram Murty's text "Problems in Analytic Number Theory". I recently encountered the following problem: If $$\lim_{x \rightarrow \infty} \frac{\pi(x)}{x/\log x } ...
3
votes
2answers
89 views

Prove, that the number of prime numbers between $p_n$ to $p_{2n}$ is $n-1$

I observed this phenomenon and checked this up to some(very small) $n$, but it seems so astoundingly trivial and consistent. I'm up for any proof/counterexample and opinion, thanks. Sorry, everyone ...
1
vote
1answer
50 views

When (and how often) is $2^k+1$ a prime power?

Fermat proved that if $N = 2^k+1$ is prime, then $k=2^n$ for some $n \geqslant 0$. In this case $N$ is known as a Fermat prime. Only five known Fermat primes exist, corresponding to $n \in ...
2
votes
1answer
54 views

Showing there are infinitely many mutually disjoint subsets of $\mathbb{N}$.

Problem: Show that there exists an infinite number of mutually disjoint subsets of the set of natural numbers. My idea: Let $P$ denote the set of all prime numbers. We know $P\subseteq\mathbb{N}$ ...
30
votes
11answers
3k views

Is the number $-1$ prime?

From my understanding it's not prime because it's not greater than $0$. So my followup question is why did mathematicians exclude $-1$? The definition of prime is having only two factors. $-1 \cdot ...
0
votes
2answers
58 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 ...
1
vote
1answer
55 views

Show that $1^m+2^m+\cdots+(p^2)^m\equiv-p\pmod{p^2}$ when $p-1\nmid m$

Can you please help of how can I approach this proof. I have seen a proof of the power sum of p in the internet but it doesn't seem very helpful. I want to show that $S_m(p^2)$ is congruent to $-p$ ...
0
votes
1answer
38 views

Does $\sum (2n)!/(n!) $ converge p-adically

Does $\sum (2n)!/(n!) $ converge p-adically, I have worked out $v_p((2n)!) \leqslant 2n/(p-1) $ similarly $v_p((n)!) \leqslant n/(p-1) $ I want to prove this using the result that it converges ...
0
votes
2answers
58 views

Does $\sum n $ converge p-adically?

Does $\sum n $ converge p-adically, I have worked out $v_p(n) \leqslant log(n)/log(p) $ not sure how to conclude from this I want to prove this using the result that it converges p-adically iff ...
0
votes
0answers
21 views

Find the number of solutions to the following congruence

Suppose that $N = p^a$, $gcd(c, p) = 1$, and that $p$ is an odd prime. $$x^e = c \pmod N$$ Prove that if any solution to the congruence exists, then there are exactly $gcd(e, p^{a}-p^{a−1})$ distinct ...
0
votes
2answers
65 views

$\mathbb Z_p^*$ is a group iff $p$ is prime

I'm trying to prove $\mathbb Z_p^*$ is a group if and only if $p$ is prime. I know that if $p$ is prime $\mathbb Z_p^*$ is a group, but how can I do the converse? In another words, if the equation ...
0
votes
1answer
33 views

Calculating p-adic valuation $v_p(n)$, using basic properties

Calculating p-adic valuation $v_p(n)$ I'm not confident with the properties of $v_p(n)$ Where $v_p(n) = $ the biggest integer $e$ such that $p^e$ divides $n$, if $n\not=0$, and $+\infty$ if $n=0$. ...
5
votes
0answers
29 views

Given $h(\mathcal{O}_{\mathbb{Q}(\sqrt{d})}) = 1$, what is the longest possible run of inert primes in that ring?

Say $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ is a unique factorization domain. A couple of primes will ramify, the rest will either split or be inert. For example, in ...
0
votes
1answer
86 views

Legendre's Conjecture!

This is my last attempt to the Legendre's Conjecture: based on my first one, it's not that difficult to follow, I'm not using logical manipulation or something like this, it's all about inequalities ...
9
votes
2answers
85 views

Is $53$ expressible in this form?

It seems as if prime numbers may always be expressed in the form $a\cdot 2^b+c \cdot 3^d$ for some nonnegative integers $b,d$ and $a,c\in \{-1,0,1\}$. Examples: $2=1\cdot 2^1+0\cdot 3^d$ $3=0\cdot ...
0
votes
0answers
32 views

Less-ugly proof of infinitude of primes of form 6N+1

While reviewing a free online algebra text I came across this problem in the sort of remedial section of the book: Prove that there are an infinite number of primes of the form $6n + 1$. I had a ...
0
votes
1answer
25 views

Euclid theory problem on number theory for p divides the binomial coefficient. [duplicate]

let p be a prime and let n be any integer satisfying 1<= n <= p-1. Prove that p divides the binomial coefficient (p,n) = p!/[(p-n)!n!] i know that p|p! but p does not divides 1/[(p-n)!n!] ...
2
votes
1answer
42 views

Greatest common divisor problem on number theory. [duplicate]

Prove that if $\gcd(x, y) = 1$ then $\gcd(x + y, x - y) = 1$ or 2. I know that any linear combination of $x, y$ is multiple of 1 since $\gcd(x, y) = 1$ then the set would be $\{1, 2, 3, 4, 5, \ldots, ...
1
vote
0answers
81 views

Does $(1093)^2|2^{1092}-1$? [duplicate]

I have this problem: Show that $(1093)^2|2^{1092}-1$. By this | I mean divide. I would like to write here my progress but I have absolutely no clue how to do show that it divides. Any ideas? ...
0
votes
1answer
23 views

Are the 2nd to the 5th bit of primes uniformly distributed

For load balancing in a project I am doing I wanted to know if the following is uniformly distributed between 0 and 15: (p / 2) % 16 Or in C: ...
2
votes
1answer
40 views

Form of Wieferich primes?

http://library.uwinnipeg.ca/people/dobson/mathematics/Wieferich_prime_theorems.html states Gallardo's result on Wieferich primes: A prime $q = 2p + 1$ with $p$ prime and $p ≡ 3 \mod 4$ cannot be a ...
5
votes
2answers
62 views

Maximize the prime sums in a table

The entries of a $3×3$ table are integers from $1$ to $9$, and each number appears exactly once. Consider the row, column, and diagonal sums of numbers in the table. Find the maximum number of these ...
0
votes
1answer
49 views

Proof that if $a$ is an integer greater than $1,$ then there are infinitely many primes of the form $p=a^n(a+1)-1,$ where $n$ is a positive integer

I'm trying to prove the following proposition: If $a$ is an integer greater than $1$ then there are infinitely many primes $p$ of the form $$p=a^n(a+1)-1, $$ where $n$ is a positive integer. I ...
1
vote
1answer
36 views

Putting a bound on sum of primes with a certain property

I'm trying to prove that the Dirichlet density of the set $X$ of primes of the form $p = n^2+1$ is zero. The only way I can think to do it is to put a bound on the sum $\Sigma_{p\in X} \frac{1}{p^s}$, ...
2
votes
1answer
44 views

If order of group is $p^2$, where $p$ is prime, how can you deduce $G$ is isomorphic to $C_{p^2}$ or $C_p \times C_p$?

Given $|G|=p^2$ then how can you deduce $G\cong C_{p^2}$ or $G \cong C_p \times C_p$ I have shown that G is abelian, not sure what to do next
1
vote
1answer
50 views

Integer factorization with sieving

I am trying to solve the Integer Factorization problem using the sieving method, and I was wonder if there been a study in this area and if there more on this topic that I can read? Note, I am not ...
0
votes
1answer
22 views

$g^i\equiv g^j (mod p)$ implies $g^{i-j}\equiv 1 (mod p)$

How do I prove this? I feel like its obvious but can't think how to do it for reason. p is a prime by the way. Is it also true that $g^i\equiv g^j (mod p^2)$ implies $g^{i-j}\equiv 1 (mod p^2)$? ...
5
votes
1answer
162 views

Help me find the flaw in my method for prime counting

I've been playing around with my own notation for estimating the number of integers relatively prime to a given primorial and I came up with a result that cannot be right. I would appreciate it if ...
2
votes
1answer
62 views

What is the value of this Infinite Product of prime numbers expression? [duplicate]

What is the value of: $$\prod_1^\infty \frac{p_i^2}{p_i^2 -1 }$$ Where $$p_i$$ are the prime numbers: 2, 3, ...
1
vote
1answer
57 views

Algorithm that decides whether collection of primes exists which satisfies 3 equations

Suppose someone gives you a list of $n$ positive numbers $(a_1, \ldots , a_n)$, together with an upper limit $N$ and asks you to find prime numbers $p_1, \ldots ,p_n$ in the range $2, \ldots , N$ ...
0
votes
1answer
20 views

Is there a probabilistic prime test with time complexity log^p (p<1)?

My question is: Is there a (possibly probabilistic) prime test with sub-logarithmic runtime complexity? Is it possible to construct one? I have found the following complexities for the most common ...
2
votes
1answer
67 views

Proof for a statement on prime numbers

I read the following statement: We can define the number $$x=2^0\cdot 3^1\cdot 5^2\cdot 7^3\cdot\ldots\cdot b^n$$ where $b$ is the $n$'th prime number. That is, $b$ is the $n$'th prime number if ...
0
votes
2answers
54 views

Prove, that the sum difference of all consecutive prime numbers from $p_1$ to $p_n$ is $p_n-p_1$

Example: $\mid (2-3)+(3-5)+(5-7)+(7-11)\mid =11-2=9$ I tried a couple of basic tricks to reach some proof but I failed.
0
votes
0answers
37 views

How to compute Dirichlet densities?

I need to calculate the Dirichlet density of the set of primes $p$ of the form $p = n^2 +1$ (in fact show it is zero), but I have no idea how to go about it. My definition of Dirichlet density of a ...
0
votes
1answer
16 views

Does the product of these Mersenne-related superparticulars converge?

If $M_n$ is the $n^{th}$ Mersenne prime, does this series converge? $$\prod_{n=1}^∞ \frac{M_n+1}{M_n}$$
0
votes
1answer
16 views

How can I find all coprime integers with constraint

I would like to generate all coprime integers $(p,q)$ such that $0 < \frac{p}{q} < N$, is there a good algorithm for that?
0
votes
3answers
50 views

Finding prime numbers in 3 equations

I have to find prime numbers P1, P2, P3 and P4 that satisfy the 3 equations below: P2 = P1 + 2 P3 = P2 + 4 P4 = P3 + 8 And I'm clueless about where to start. Which mathematical theorem/method (if ...
0
votes
1answer
26 views

Product of a prime and other number expressed in two ways are equal

Let $p \in \mathbb P$ be an odd prime and let $1\leq a \leq p-1$ be such a number that $$a p = \left\lceil \sqrt{a p}\right\rceil ^2-\left\lceil \sqrt{\left\lceil \sqrt{a p}\right\rceil ^2-a ...
1
vote
2answers
82 views

How to prove $\underset{p\leq n}{\prod}p^{\frac{1}{p-1}}\leq 2n$?

I know that ($p$ prime) (1) $$\underset{p\leq n}{\prod}p^{\frac{1}{p-1}}\sim n$$ Is there a way to prove (2) $$\underset{p\leq n}{\prod}p^{\frac{1}{p-1}}< 2n$$ ? Thanks!
4
votes
3answers
114 views

When is the number of $N$'s factors $1 + \sqrt{N}$?

(Answer: Only $N = 4$ and $N = 16$.) The following question arose in a course for pre-service and in-service elementary school teachers: For what $N \in \mathbb{N}$ is it the case that the ...
2
votes
2answers
59 views

Prove, If the sum of the first $n$ prime is also a prime then it is also a hypotenuse of a primitive Pythagorean triples

I checked this for all the primitive Pythagorean triples $<300$. Some examples would be: a. $2+3=5$, b. ...
2
votes
0answers
46 views

Numbers $m,n$, such that $a^m+ab+b^n$ is always composite

Are there integers $m,n\ge 2$, such that $$a^m+ab+b^n$$ is composite for all integers $a,b\ge 2$ ? I checked the pairs with $2\le m\le 100$ and $2\le n\le 100$ and always found a prime of the form ...
0
votes
1answer
33 views

$q=1+k256$ and q is a prime,does $q|2^{k}+1$

$q=1+k256$ and q is a prime,$2^{k}+1>>q$, does $q|2^{k}+1$ I am stuck. From fermat's little theorem $2^{q-1}=2^{256k}\equiv 1 mod (q)$ assuming $x=2^{k} $, the solution to $x^{256}\equiv 1 ...
0
votes
0answers
32 views

Theorem on the length of factor chains

Given any prime number $p_i$, define the base factor chain $B(p_i)$ as the sequence of numbers $2,3,4,5,6,...,p_i-1$ reduced into their lowest prime factors. i.e $B(17) = ...
1
vote
1answer
67 views

how to solve $x^2 \equiv a \pmod{ n}$, where $n = p_1 p_2 \dots p_r$

Let $p_1,p_2, \dots , p_r$ be different odd prime numbers, and $n$ be the multiplication of them $n = p_1 p_2 \dots p_r$. Let $$a \in \mathbb{Z} / n \mathbb{Z}$$ and assume that $\gcd(a,n)$ is ...