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
2answers
112 views

$(a+b)^p = a^p+b^p$ if $p$ prime and $a,b \in \mathbb{F}_p$

Can someone please explain why \begin{align} (a+b)^p = a^p+b^p \end{align} if $p$ is prime number and $a,b \in \mathbb{F}_p$ I tried to proof it that way \begin{align} (a+b)^p = \sum_{j=0}^{p}{p ...
0
votes
0answers
69 views

Proof using the Fundamental Theorem of Arithmetic

Prove that $\sqrt{27} \not\in\Bbb Q$ I have to prove that $\not\exists m, n\in \Bbb Z$ that satisfies the following equation: $m,n \in \Bbb Z : \sqrt{27} = {m\over n} \implies 27 = {{m^2}\over{n^2}} ...
1
vote
2answers
89 views

Proving that $\sum_p\frac{1}{p+1}$ diverges

How does one prove $$\sum_{p\in\Bbb P}\frac1{p+1}=\infty.$$ Where $\Bbb P$ denotes the set of prime numbers. I have attempted forming an inequality by playing around with Euler's work on the ...
2
votes
2answers
47 views

Is there a possibility for two different primes to have any of its powers to be the same?

Say there are two primes $P_1$ and $P_2$ where $P_1 \neq P_2$. Is there a possibility for some $m$, $n$ ($m \neq 0, n \neq 0$) such that $P_1^m = P_2^n$.
1
vote
1answer
85 views

Lower bound for second Chebyshev function

I was wondering is there any simple way to find nice lower bound for second Chebyshev function given by formula: $$\psi(x)=\sum_{p\le x} \left\lfloor \frac{\ln x}{\ln p} \right\rfloor\ln p$$ that is ...
0
votes
2answers
150 views

prove that $n >2$ and $n$ is a prime then $n$ is odd

$n > 2$ and $n$ is a prime number then $n$ is odd. Prove by contradiction assume $n$ is even then there is some $k\in\Bbb N, n = 2k$ then $n >2, 2k > 2 , k > 1$ Is this a sufficient ...
5
votes
9answers
456 views

Which is the greatest possible natural number that divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$?

Which is the greatest possible natural number that definitely divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$? This one is from my module, comes as a fill in the blanks with ...
-3
votes
3answers
120 views

Prove that $S=1+2+3+…+n$ is not a prime number

I need help: I don't know how to prove that $S=1+2+3+\cdots+n$ is not a prime number, for any $ n \ge 3 $. Thank you in advance.
0
votes
1answer
33 views

If $\sum_{k=1}^{p-1}\frac{1}{k}=\frac ba$ where $\frac ba$ is an irreducible fraction, then $b$ can be divided by $p^2$?

Question : Is the following true for any prime number $p\ge 5$ ? If $\sum_{k=1}^{p-1}\frac{1}{k}=\frac ba$ where $\frac ba$ is an irreducible fraction, then $b$ can be divided by $p^2$. ...
3
votes
2answers
73 views

$a_1=k,a_{n}=2a_{n-1}+1(n\geq 2).$ Does there exist $k\in\mathbb N$ such that $a_n,n=1,2,3,\cdots$ are all composite numbers?

Let $a_1=k,a_{n}=2a_{n-1}+1(n\geq 2).$ If $k=1$ then $a_n=1,3,7,15,31,63,\cdots$ here $3,7,31$ are prime numbers. I'm interested in this problem: Does there exist $k\in\mathbb N$ such that ...
1
vote
3answers
90 views

Last two digits of $2^{11212}(2^{11213}-1)$

What are the last two digits of the perfect numbers $2^{11212}(2^{11213}-1)$? I know that if $2^n-1$ is a prime, then $2^{n-1}(2^n-1)$ is a perfect number and that every even perfect number can ...
2
votes
2answers
488 views

If $n$ is composite, so is $2^n-1$ [duplicate]

Possible Duplicate: Simple Mersenne prime divisibility proofs I'm taking elementary number theory and there is this one question that I don't know where to start at... Please help me, ...
0
votes
2answers
103 views

Generating function for the nth prime

Is there a generating function for nth prime that is easy to deal with? i.e. is there a simple closed form for the series $p_1x + p_2x^2 + ...$ or of the form $\sum_{n = 1}^\infty x^{p_n}$
8
votes
1answer
299 views

Are differences between powers of 2 equal to differences between powers of 3 infinitely often?

Consider the equation $2^a-2^b=3^c-3^d$ where $a>b>0$, $c>d>0$, and $a,b,c,d$ are all integers. A computer search for solutions with $a,c\le20$ only finds 8-2=9-3, 32-8=27-3, and ...
7
votes
0answers
179 views

Prime numbers, analysis of polylogarithms

Can any interesting results concering prime numbers be obtained using the analytic properties of the polylogarithm, similar to how analytic methods are used on the zeta function to obtain results ...
1
vote
1answer
125 views
1
vote
0answers
69 views

Functions generating prime numbers in math packages

Does anyone have an idea on how prime number generating functions such as Prime[n] in Mathematica generate the $n^{th}$ prime number?
4
votes
2answers
2k views

Finding number with prime number of divisors?

The problem is to find the number of numbers in [l,r] that have prime number of divisors. Example for $l=1,r=10$ The answer is $6$ since $2,3,4,5,7,9$ are the numbers having prime number of divisors ...
2
votes
2answers
95 views

How to prove a given number is prime?

How would I go about showing a number is prime, especially a very large number. Say I wanted to show that 43112621 is a prime number. How would I go about doing this without showing no other prime ...
1
vote
1answer
124 views

Counting primes by counting numbers of the form $6k \pm 1$ which are not prime

Again, pondering on twin primes, I came upon the following result. It baffles me a bit, so could someone give more intuitive reasoning why it works. First, define a function $P_6$ as ...
6
votes
6answers
568 views

How to efficiently compute $17^{23} (\mod 31)$ by hand?

I could use that $17^{2} \equiv 10 (\mod 31)$ and express $17^{23}$ as $17^{16}.17^{4}.17^{3} = (((17^2)^2)^2)^2.(17^2)^2.17^2.17$ and take advantage of the fact that I can more easily work with ...
4
votes
4answers
400 views

A short or elegant proof for if $p | n^2$ then $p | n$ when $p$ is prime?

Let $n, p \in \mathbb{Z}^{+}$ such that $p$ is prime. Prove $p | n^2 \Rightarrow p | n$. What is a short or elegant proof to this? Some ideas are given at the question Prove that $\sqrt 5$ is ...
14
votes
1answer
287 views

Sum of reciprocals of primes factorial: $\sum_{p\;\text{prime}}\frac{1}{p!}$

The series $$\sum_{p\;\text{prime}}\frac{1}{p}=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\cdots$$ diverges as is well known. How about the following? ...
4
votes
4answers
294 views

By definition, how is a prime number represented?

Even numbers can be easily represented as $2n$. Odd numbers as $2n+1$. An exactly divisible operation can be defined as $n = dq$. But, is there an specific way of representing a prime number, ...
2
votes
0answers
110 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
4
votes
0answers
66 views

Is there always a prime number in the form of $4k+1$ between $[n, 2n]$ for every large enough $n$?

Is there always a prime number in the form of $4k+1$ between $[n, 2n]$ for every large enough $n$? I guess it is known as a classical result. Is there any reference for it? Thanks!
1
vote
1answer
210 views

simple proof of a theorem that is weaker than chen's theorem?

I want to see a simple proof of a theorem that is weaker than chen's theorem. Thus let $m,n$ be positive integers. An m-almost prime is a squarefree integer that is the product of at most $m$ primes. ...
2
votes
1answer
95 views

Is there always $k \in \Bbb N$ such that $g^{k+1} \equiv g^k+1 \pmod p$, where $p$ is a prime number?

Let g be a generator of the group $\Bbb Z_p^*$. Show that there is a $k \in \Bbb N$ such that $g^{k+1} \equiv g^k+1 \pmod p$, where $p$ is a prime number. Excuse me please for bad interpretation of ...
2
votes
1answer
258 views

A curious plot of Primes (II)

Here is the plot of a function $f(x)$ such that: $$ f(x) = \frac {P_ {\lfloor 2 x \rfloor}} {P_ {\lfloor 2 x \rfloor - 1}} $$ where $P_k$ is the $k^{\mathrm{th}}$ Prime Number for x in range [1,300]. ...
1
vote
1answer
246 views

Proving Goldbach's conjecture (hypothetically)

Part $1$. If $\pi(n) \sim \frac{n}{\ln(n)}$ by the prime number theorem, can we treat $\frac{1}{\ln(n)} $ as the probability that a number less than $n$ is a prime number? Say we have some operation ...
4
votes
4answers
1k views

The n-th root of a prime number is irrational

If $p$ is a prime number, how can I prove by contradiction that this equation $x^{n}=p$ doesn't admit solutions in $\mathbb {Q}$ where $n\ge2$
0
votes
2answers
99 views

How to show the existence of a number with certain divisibility conditions between two multiples?

How can we show that between two even natural numbers they're exists a natural number that isn't even? How can we show that they're exists a natural number that is odd and not divisible by 3, between ...
4
votes
2answers
517 views

Show that there are infinitely many prime numbers ending in 3 or 7 (when written in decimal)

I have been struggling with this problem. I have already shown that every integer ending in $3$ or $7$ (when written in decimal) has a prime factor which also ends in $3$ or $7$ (using $n = 3$ or $7$ ...
1
vote
0answers
190 views

Proving there exists prime numbers between the squares of prime numbers

Conjecture: $\forall $ $p_{n}$, $p_{n+1} \in \mathbb{P}$, $\:$ $p^2_{n+1} = p^2_{n} +\omega_{n} p_{n} + \phi_{n} : \phi_{n} , \omega_{n} \in \mathbb{N} $ and $ \phi_{n} < p_{n}$, $\:$ ...
8
votes
1answer
146 views

$pq\equiv 1\pmod 4$, how to find $p,q\bmod 4$?

Somebody asked me a question, I have no idea about it, the question is: If a positive integer $n\equiv 1\pmod 4$ is the product of two primes, (denotes $n=pq,$ such as a RSA number) but we don't ...
2
votes
1answer
129 views

Does there exist a prime number within the interval?

Conjecture $\forall p_{n}\in \mathbb{P} : n\geq3, \: \exists p_{m}\in \mathbb{P} : 3p_{n} - 4 \geq p_{m} > \sqrt{2(p^2_{n+1} - 1)} $ How would you go about proving/disproving this?
1
vote
1answer
232 views

The proportion of numbers not divisible by prime numbers with respect to primorial numbers.

Looking at the interval of the natural numbers $ [1, p_{n}$#$] $; $\frac{1}{2}$ of the elements of this set will be even, and $\frac{1}{2}$ will be odd. $\frac{1}{3}$ of the elements of this set will ...
5
votes
1answer
188 views

A conjecture about the difference between consecutive primes with respect to a prime number squared.

Conjecture If we have two consecutive prime numbers $p_{a}$ and $p_{a+1}$, and two other consecutive primes $p_n$ and $p_{n+1}$, so that $p_{a} < p_{a+1} < p^2_{n+1}$, then $p_{a+1} - ...
3
votes
1answer
83 views

Find $a\in\mathbb{N}$ such that $n^4+a$ is not prime $\forall n\in\mathbb{N}$

How would I go about finding such an $a$? I've been thinking it is something to do with modular arithmetic, but don't know what base to consider.
1
vote
1answer
137 views

The name and proof of a conjecture on prime intervals

Conjecture: There exists at least one prime number $p_{m}$ : $ap_{n} < p_{m} < (a+1)p_{n}$, $\forall$ $a \in \mathbb{N}$ and $\forall$ $p_{n}$ $\in \mathbb{P} $ if $(a+1)p_{n} < ...
2
votes
1answer
185 views

Challenging the Chebychev function / prime number theorem?

The prime number theorem accords with the following equation for the first Chebychev function that: $$\lim_{x\rightarrow\infty}\frac{\vartheta(x)}{x}=1 \qquad (1)$$ According to Muñoz García, E. and ...
4
votes
3answers
470 views

Characterising reals with terminating decimal expansions

Show that a number has a terminating decimal expansion if and only if, it is rational and when in lowest terms, its denominator is coprime to all primes other than $2$ and $5$. This is an unsolved ...
0
votes
1answer
207 views

Gaussian prime proof

Prove or disprove that if $a+bi$ is a Gaussian prime, where a and b are nonzero, then $N(a+bi)$ is a rational prime. I am pretty sure that there is a theorem that states this, but I'm not sure how ...
2
votes
0answers
107 views

The intersection of two sets of natural numbers defined via primes is infinite

Any given prime $P \in \mathbb P$ is either of the form $$ P \equiv -1 \mod 6$$ or $$ P \equiv 1 \mod 6.$$ In other words, every prime greater than 3 can be expressed in the form $$P = 5+6n \vee 7 + ...
8
votes
2answers
1k views

Why does $\phi(pq)=\phi(p)\phi(q)$?

In an RSA paper I am reading it is assumed that where $p$ and $q$ are distinct prime numbers: $\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$ I would love to know why/how this is so? Is there some way to prove ...
7
votes
0answers
108 views

For primes $P_1$ and $P_2$, exists a prime $P_3$ that both $P_i + 6P_3$ is a prime

I was thinking about twin primes and I came to ask this question: If we have two distinct primes $P_1$ and $P_2$ which are both greater than $3$, then does there always exist a prime $P_3$ such that ...
1
vote
1answer
110 views

Let $p_k$ be the $k$th prime, can it be shown for $p \ge 5$, that there is not always a twin prime between $p_k^2$ and $p_{k+1}^2$?

For any primorial $p_k \ge 3$, $p_k\#$, there are $$\prod_{2\le{i}\le{k}} (p_i-2)$$ distinct instances of $x,x+2$ that are relatively prime to $p_k\#$. If any of these pairs are less than ...
6
votes
2answers
99 views

On primes between $k$ and $k!$

I have the following homework question: "Show that for $k\geq 4$ between $k$ and $k!$ there always exists a prime number of the form $4n+3$." How can one prove it?
0
votes
1answer
65 views

Solve: $ \dfrac{x}{k_1} + \dfrac{y}{k_2}=z $ when $ x+y \neq z$

If $\gcd(x,y,z)>1$, any hint on how to find all the non-zero pairs $(k_1, k_2) \in \mathbb{Z^2} $ such that $ \dfrac{x}{k_1} + \dfrac{y}{k_2}=z $ when $ x+y \neq z$?
4
votes
2answers
185 views

An interesting (unknown) property of prime numbers.

I don't know if this is the right place to ask this question. Please excuse my ignorance if it is not. I like to play with integers. I have been doing this since my childhood. I spend a lot of time ...