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
92 views

Proof of $p_n<n^2$ by Elementary Means

Is there any proof of the inequality $p_n<n^2$ (for all sufficiently large $n$) by elementary means and without using Prime Number Theorem? I searched in google but in vain. The results that I ...
12
votes
1answer
182 views

Primes in $\lfloor a^{n} \rfloor$

Motivated by the question Is there any result, that says that $\lfloor e^{n} \rfloor$ is never a prime for $n>2$?, take a real number $a>1$ and consider the sequence $\lfloor a^{n} \rfloor$. ...
3
votes
1answer
62 views

Is this number composite or prime: $2000^{2002} + 2000^{2000} + 1$?

Is this number composite or prime? $$2000^{2002} + 2000^{2000} + 1$$ I want to find an easy approach to this problem.
5
votes
1answer
41 views

Normalizer and centralizer are equivalent when $p$ is the smallest prime dividing $|G|$

Let $p$ be the smallest prime dividing $|G|$, and suppose that some $P \in \mathsf{Syl}_p(G)$ is cyclic. Prove that $N_G(P) = C_G(P)$. So I let $G=p^\alpha m$ $p$ does not divide $m$. P is cyclic, ...
0
votes
1answer
46 views

Is it an open problem about Riemman Hypothesis non-trivial zero? [duplicate]

Let's assume RH was correct, and $1/2+Ki$ is any one of non-trivial zero of $\zeta$, is following problem open? 1) $K$ is irrational number 2) $K$ is transcendental number
0
votes
1answer
23 views

can Sophie Germain prime be arbitrarily many?

We know that there exists arbitrarily long prime arithmetic progressions by BEN-TAO. Together with Dirichlet's theorem on arithmetic progressions, can we address that Sophie Germain prime number be ...
3
votes
2answers
95 views

Find prime factorization in ring $Z[\frac{-1+ \sqrt{3}}{2}]$

Find prime factorization of the number $13$ in the ring $Z[\frac{-1+ \sqrt{3}}{2}]$ My progress: Let $w=\frac{-1+ \sqrt{3}}{2}$ and let $N(z)=z \bar z$ be the norm function. $N(a+bw)=a^2-ab+b^2$ ...
2
votes
3answers
740 views

Proof of Wilson's Theorem

In first proof of Wilson's theorem on wikipedia. It is written that "So for each of these integers a there is another b such that ab ≡ 1 (mod p)." (Here 'a' and 'b' ...
8
votes
2answers
188 views

On the difference between consecutive primes

Let $(p_n)$ be the sequence of prime numbers and $g_n = p_{n+1} - p_n$ Question: Is it known that $g_n \le n$? Remark: it's known that $g_n < p_n^{\theta}$ with $\theta = 0.525$ for $n$ ...
2
votes
2answers
314 views

Constructing pseudoprimes to the base 3.

When $n$ is a pseudo prime to the base 2, $2^{n}-1$ is also a pseudo prime to the base 2. This implies there are infinitely many pseudoprimes to the base 2. Then, how can I construct pseudoprimes to ...
4
votes
1answer
55 views

Eulers totient function divided by $n$, counting numbers in the set [1,m] that are coprime to n

If we divide Euler's totient function $\omega(n)$ by $n$, we obtain a fraction. If we multiply this fraction by any natural number $m$ which gives us another natural number $p$, is it true that $p$ is ...
1
vote
2answers
39 views

If $m$ and $n$ are integers with $\gcd(m,n) = 1$, prove that $\sigma(mn)= \sigma(m)\sigma(n)$.

If $m$ and $n$ are integers with $\gcd(m,n) = 1$, prove that $\sigma(mn)= \sigma(m)\sigma(n)$. I am thinking about using the formula for $\sigma(p^k)$ where $p$ is prime. It follows from the ...
0
votes
1answer
58 views

Search for very large prime (greater than $2^{57885161} − 1$) between Crystal Numbers

Denote $p[i]$ as the $i$th prime. In my opinion, the following is true: Prime Gap Axiom There are always distinct prime factors for $\{p[i],p[i]+1,p[i]+2, \dots , p[i+1]\}$. Question 1 How to ...
1
vote
1answer
36 views

Probability distribution of count of factors for all numbers

Is the following known? Define "factor count" as the number of prime factors of the number, minus 1. For example: Prime numbers have a factor count of 1-1 = 0 4 has a factor count of (2 and 2)-1 = ...
3
votes
2answers
23 views

Math for Computer Science

I have a couple of questions on the material in "Mathematics for Computer Science" by Eric Lehman and Tom Leighton. Q1. This is a theorem in the book: Theorem 24. Let $p$ be a prime. If $p|a_1a_2 ...
1
vote
2answers
54 views

Prime numbers and $\sqrt{10301}$

On my exam recently, we had the following question: Use the prime number theorem to estimate the number of primes less than $\sqrt{10301}$, and hence, give a concise argument whether 10301 is prime ...
2
votes
0answers
70 views

Conjecture on sum of powers

Let $n$ be an odd number, $x,y$ integers and $p$ a prime number. Now, suppose that $p\ne n$ and $$ p|\frac{x^n+y^n}{x+y} $$ Then, I have been observed that $p \equiv 1 \pmod{n}$. This is, all of the ...
0
votes
1answer
39 views

Find a real $β$ such that $(β^{2^{p-1}}+1)/(β^{2^{p-2}}(2^{p}-1))$ is an integer [closed]

Let $p$ a prime number. Find a real $β$ such that $(β^{2^{p-1}}+1)/(β^{2^{p-2}}(2^{p}-1))$ is an integer.
1
vote
1answer
33 views

Something similar to Euler's theorem

If $p$, $q$ are not equal primes. $n=pq$, $\varphi(n) = (p − 1)(q − 1)$, $d = \gcd(p − 1, q − 1)$. Is it true that for any $a$ such that $\gcd(a, n) = 1$ holds $a^{\frac{\varphi(n)}{d}} \equiv 1 ...
2
votes
2answers
94 views

Finding prime solutions to $100q+80 = p^3 + q^2$

Finding prime solutions to $100q+80 = p^3 + q^2$ Does them being prime imply some patterns on division modulo 3 or some other integer? How is this done?
2
votes
1answer
63 views

Prove that $p \ge 5$ is prime, then the remainder of $p$ upon division by $6$ is $1$ or $5$.

An example in my textbook, but I'm not quite sure how to set this one up, because of the $p \ge 5$ part. How do I start it off?
3
votes
0answers
71 views

How prime numbers are related to special functions?

We know that the Riemann zeta function is defined as $$\zeta(s)=\sum_{n=1}^\infty\frac{1}{n^s},$$ for all $\Re(s)>1$. Because of Euler product formula we also know that $$\zeta(s) = ...
2
votes
3answers
74 views

Finding all natural $n$ such that $2^n+2^{2n} +2^{3n}$ has only $2$ prime factors.

Find all natural $n$ such that $2^n+2^{2n} +2^{3n}$ has only $2$ prime factors. I've tried checking the first 6-7 $n$'s on wolframalpha, but I don't see any patterns for even nor odd $n$'s. At first ...
2
votes
1answer
24 views

distribution of gaussian primes

here is a naive question that so far I don't have already found somewhere else. In the following, I consider the norm on gaussian integers with $N(a+ib)=a^2+b^2$. Consider prime gaussian integers ...
0
votes
2answers
50 views

Any technique to manually find the prime decomposition of a number less than 3000?

I've seen a question in a math exam, asking to find the prime decomposition of 2014. It's 2*19*53. I found it odd and a little fastidious at first to try to find the multiples of 1007, trying to ...
2
votes
1answer
51 views

Is there a way to relate prime numbers and the fourier transform

According to what I know about Fourier transforms, any continuous periodic signal can be represented as a combination of sine and cosine functions. To me, this looks analogous to the "Fundamental ...
41
votes
13answers
9k views

For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.
8
votes
2answers
205 views

Does $\sum\limits_{n=1}^{\infty}\frac{1}{P_n\ln(P_n)}$ converge to the golden ratio?

The sum $\displaystyle\sum\limits_{n=2}^{\infty}\frac{1}{n\ln(n)}$ does not converge. But the sum $\displaystyle\sum\limits_{n=1}^{\infty}\frac{1}{P_n\ln(P_n)}$ where $P_n$ denotes the $n$th prime ...
4
votes
2answers
49 views

$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$

Using elementary means, show that the $(n+1)^{\textrm{st}}$ prime is less than $2^{2^n}$ please do not use fancier stuff like the prime number theorem or beyond. using this how can you show that ...
2
votes
1answer
27 views

Calculating the power of prime in factorial by changing base

The greatest power $k$ of a prime $p$ in the prime factorization of $n!$ is equal to $\frac1{p-1}(n-s(n)_p)$, where $s(n)_p$ is the sum of digits of $n$ when represented in base $p$. How to ...
0
votes
1answer
7 views

Discrete algebra and exponents (See body text)

Let $a,b\in\mathbb{Z}^+$. If $a \equiv b\bmod 49$, and $\gcd(a,49) = 1$. How can I find any positive integer $n > 1$, so that $b^n\equiv a\bmod 49$? I'm completely stumped by this. I've been ...
1
vote
1answer
65 views

Question about any 2 distinct primes and the difference between their multiples

I've been thinking about the following situation. Let $p$,$q$ be two distinct primes. Let $a,b \le pq$ be any two numbers such that $a \ge b$ where $p$ divides $a$ or $b$ and $q$ divides the other. ...
0
votes
1answer
36 views

Decryption of a RSA encrypted message is not working.

Using RSA with e=13 (encrypting power), d=17 (decrypting power) & n=33 (RSA modulus) I noticed that once I decrypted the encrypted message it would be different then the original message. Why is ...
4
votes
1answer
84 views

Convergence of infinite product of prime reciprocals?

Where pn is the nth prime number, does the infinite product $$\prod_{n=1}^{\infty}\left(1-\frac{1}{p_n}\right)$$ converge to a nonzero value? (Any help would be much appreciated!)
0
votes
0answers
26 views

The representations of numbers by decimals

I'm looking for books that talk about the representation of the integers by decimals, more specifically for prime numbers. I can't found anything yet, I read something in "AN INTRODUCTION TO THE ...
1
vote
2answers
28 views

Can we find an integer $m$ such that: $2^{2p-2}-2^{p}+3=m²$

Let $p$ a prime number. Can we find an integer $m$ such that: $$2^{2p-2}-2^{p}+3=m²$$
1
vote
3answers
50 views

What makes the Mersenne primes formula more special than any of these formulas?

Mersenne Primes Formula $2^n-1$ gives false results just like any of those ones: $3^n-2, 4^n-3, P_1\cdot P_2+P_1+P_2$, or $5^n-4$ and so on.. I think that each of those formulas(including ...
4
votes
2answers
46 views

Can we find $n$ such that $p|2^n-1$ for a given prime $p.$

For a given prime $p$ can we find a positive integer $n$ such that $p$ is a divisor of $2^n-1.$ I know, choosing a large $n$ we can do this. But is there any proof for this? I have no idea for start a ...
1
vote
1answer
44 views

to count the intervals

A finite set of two or more consecutive natural numbers is called a "co-prime interval" if there is no number in it that is co-prime to all other numbers in the set. Given a range [A, B], I would ...
0
votes
2answers
91 views

What is the number of digits of this number: $2^{333111160}$? [duplicate]

My question is: What is the number of digits of this number? : $$2^{333111160}$$
0
votes
4answers
71 views

Is it true that $2^{p}-1$ is a prime number?

Let $p$ be an odd prime such that $$p \equiv 1 \pmod{4}$$ and $p$ and $p-2$ form a twin prime pair. My question: Is it true that $2^{p}-1$ is a prime number?
4
votes
2answers
84 views

Does there exist an $a_0$ such that the sequence $a_{n+1} = 2a_n + 1$ is prime for all $n \ge 0$?

I believe I see that $a_n = 2^n(a_0+1) - 1$ but am somewhat uncertain where to proceed afterwards. I am a complete beginner at number theory and would appreciate it if someone could point me in the ...
2
votes
2answers
72 views

Proving that if $p$ is a prime number then $gcd (p, (p-1)!) =1$

I am just making sure whether this is a valid proof: Since $p$ is a prime number, then $p$ is only divisible by $1$ or $p$ Suppose we want to take the $gcd (p,a)$ with a, an arbitrary ...
0
votes
2answers
54 views

Which of the following is true?

Let $\hspace{0.2cm}$$p,q,r$$\hspace{0.2cm}$ be prime numbers greater than 100,then which of the following is true? $3|p^2+q^2+r^2$ $q|p^5$ There exists integers $x,y$ such that ...
1
vote
2answers
24 views

If $p,q$ are prime, $q$ odd $p \not\equiv 1 \pmod q$, is there an integer $x$ such that $p\mid 1+x+\ldots+x^{q-1}$

Suppose $p,q$ are two distinct prime numbers, $q \geq 3$ and $p \not\equiv 1 \pmod q$. Then I have the following problem: Prove that there is no integer $x \in \mathbb{Z}$ such that ...
4
votes
1answer
554 views

Factorising into Gaussian primes

I'm trying to factorise the Gaussian integer $z =11 - 3i$ into Gaussian primes. Taking the Euclidean norm on $z$ is $\nu (z) = 130$ which factorises into $2 \times 5 \times 13$ and so I'm assuming I ...
0
votes
1answer
27 views

About a recurrence equation of prime numbers

Let $p$ be a prime. Consider the recurrence equation $$s_{n}=(s_{n-1}²-2)(mod(2^{p}-1))$$ where $s₀=4$ My question is: Can we write this recurrence as follow? $$s_{n}=(2^{p}-1)q+(s_{n-1}²-2)$$ ...
1
vote
2answers
59 views

Can this be solve using modular arithmetic? $k$ is prime $\Rightarrow$ $8k+1$ is prime

Is the following statement true or false? $\forall k \in \mathbb{N}, k$ is prime $\Rightarrow$ $8k+1$ is prime The answer is that the statement is false because if $k=7$, then $k$ is prime but ...
3
votes
1answer
33 views

Can we have $\sum_{n\leq [x]}e^{-\sqrt{\frac{\log x}{r}}}\ll \frac{x}{e^{c \sqrt{\log x}}}$ for some constant $c>0$, where $x>1.$

Let positive interger $n$ is square-free, that is $n=p_1p_2\cdots p_r$ some $r$. Can we have $$\sum_{n\leq [x]}e^{-\sqrt{\frac{\log x}{r}}}\ll \frac{x}{e^{c \sqrt{\log x}}}$$ for some constant ...
0
votes
1answer
27 views

Primes Involved in GCD

If p is a prime number, prove that gcd(p, (p-1)!) = 1 So, I've tried using the fact that 1 = px + (p-1)!y, where x,y are integers, but from there I'm stuck and don't really know how to work with the ...