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

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, ...
1
vote
0answers
150 views

Remarks on a Previous Post

Recently I have been reading this post and I have noted something significant in the fake argument. As one can easily see that the basic idea behind the argument had been to show that the sequence ...
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 ...
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 ...
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

Show that if $p$ is an odd prime, show a power $p^k$ can never be a perfect number

Show that if $p$ is an odd prime, show a power $p^k$ can never be a perfect number. I am little confused about this problem, any insight?
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 ...
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$ ...
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 ...
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
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 ...
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?
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 ...
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 ...
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
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 ...
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 ...
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 ...
0
votes
1answer
6 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 ...
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 ...
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
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 ...
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 ...
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}$$
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 ...
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 ...
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 ...
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. ...
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
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?
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 ...
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 ...
0
votes
0answers
34 views

Primality of Stirling numbers of second kind

Apart from the Mersenne primes $M_p=2^p-1=\begin{Bmatrix}p+1\\2\end{Bmatrix}$, and the four primes $\begin{Bmatrix}n\\4\end{Bmatrix}$ where $n$ is given in http://oeis.org/A100958, are there other ...
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 ...
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 ...
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?
2
votes
1answer
34 views

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$

If $p$ is prime and $\sigma(p^k) = n$, then $p\mid (n-1)$. proof: Suppose $\sigma(p^k) = [p^{k+1} -1]/(p-1) = n$. Then $n-1 = [p^{k+1} -1]/(p-1) - 1= [p^{k+1} -1 - (p-1)] /(p-1) = [p^{k+1} - ...
1
vote
1answer
45 views

Divisibility and Primes

Suppose that $p,q,r$ are prime numbers and $p$ is odd. If $p\,|\,(2q+r)$ and $p\,|\,(2q-r)$, prove that $q=r$. So I'm trying to use the definition of greatest common divisor to come up with two ...
0
votes
3answers
34 views

Canonical decompositions and product of primes

Let $S$ be the set of natural numbers $n$ that have exactly $9$ positive divisors. Describe all possible canonical decompositions (as products of primes) of elements of $S$.
0
votes
0answers
63 views

Prime Reflections

How would you describe the following pattern?: For each primorial from 30 onward, there exists a pattern in the arrangement of the prime factors of the composite numbers which I call "the mirror ...
0
votes
1answer
42 views

A function that maps a value to a large prime

I'd like to ask whether there is any function that maps a value to a large prime in deterministic way, so this function always maps the same value to the same large prime. The large prime here ...
1
vote
1answer
73 views

Sum of inverse prime numbers

How can the following equation be proven? $\sum\limits_{p \le n; p \in P} \frac{\ln p}{p} \sim \ln(n) + O(1).$ I just wanna understand this sum Sum of reciprocal prime numbers