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

0
votes
2answers
184 views

Are there smaller orders (cardinalities) of infinity?

I am using this source as a basis for the language to ask this question. Considering the topic of degrees of infinity, are there smaller degrees than ℵ0 (aleph null, also called ω)? ...
1
vote
1answer
109 views

Necessary and sufficient condition for a number to be regular

Background: A number is said to be (sexagesimally) regular if its reciprocal has a finite sexagesimal expansion (that is, a finite expansion when expressed as a radix fraction for base 60). With the ...
8
votes
2answers
2k views

How to prove $\phi(mn) > \phi(m)\phi(n)$ if $(m,n) \ne 1$

I need to prove that $$\phi(mn) > \phi(m)\phi(n)$$ if $m$ and $n$ have a common factor greater than 1. I have read up on the case where $m$ and $n$ are relatively prime, then ...
0
votes
2answers
161 views

Prime number minus 1 is an even number?

Is it true that for every prime number $p$ (except $p = 2$), that $p-1$ is an even number? I tried it in R (code below) for the first 168 primes (found on wikipedia) and it seems to hold, but I'm not ...
2
votes
2answers
179 views

Proving $2^{\varphi(n)}\ge n$

To show $n\in\mathbb{N}\setminus \{6\}\Rightarrow 2^{\varphi(n)}\ge n$ I can't follow the proof from http://mathematicalspectacles.blogspot.de/2012/05/interesting-study-of-zsigmondy-primes.html ...
16
votes
3answers
557 views

Solving $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$

Find all positive integers $k$, positive integers $e_i$, and distinct prime numbers $p_i$ for $1\le i\le k$, such that $$p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}.$$ Is this ...
7
votes
2answers
148 views

At least 99% of these numbers are composite

This is from a contest preparation: Prove that at least 99% of these numbers $$10^1+1,10^2+1, 10^3+1, ..., 10^{2010}+1$$ are composite. The problem is from 2010, obviously. I was ...
7
votes
4answers
216 views

Is $0$ a composite number and $-1$ a prime number?

If in the set of natural numbers, all prime numbers $p$ have only two divisors, $1$ and $p$, and all composite numbers have at least three divisors, then can we also use these definitions for the set ...
4
votes
1answer
87 views

Question about GIMPS (Great Internet Mersenne Prime Search)

Not sure if this is really an adequate question here, but I found no other place to turn. I'll understand if this gets closed. I recently learned about the GIMPS project, and installed it on my ...
20
votes
1answer
376 views

Nature of the series $\sum\limits_{n}(g_n/p_n)^\alpha$ with $(p_n)$ primes and $(g_n)$ prime gaps

Let $p_n$ denote the $n$th prime number and $g_n=p_{n+1}-p_n$ the $n$th prime number gap. This is to ask for which values of $\alpha$ the series $S_\alpha$ converges or diverges, where ...
2
votes
2answers
73 views

Seven expressions involving $F_n$ an $L_n$ that are always composite

Prove that if $F_n$ an $L_n$ are Fibonacci and Lucas numbers respectively, and $n>2$, then $$F_{n-2}\times F_{n-1}\times F_{n+1}\times F_{n+2}-15$$ $$F_{n-2}\times F_{n-1}\times ...
1
vote
3answers
53 views

Demonstration congruences

Assuming that $m=p_1^{\alpha_1}...p_r^{\alpha_r}$. Show that $$a\equiv b\pmod m\Longleftrightarrow a\equiv b\pmod {p_i^{\alpha_i}},\;i={1,...,r}$$ I always thought very beautiful statements that ...
6
votes
1answer
124 views

Prove or disprove that ${F_{n}^2} + 43$ is always a composite

This is a kind of follow-up to another question, but in order not to burden that question and its answers with new comments, I decided to create this separate question. Also, it looks this problem is ...
7
votes
1answer
149 views

Prove or disprove that ${F_{n}}^2 + 41$ is always a composite

The problem: Prove or disprove: If $F_{n}$ is the $n^{th}$ Fibonacci number then $${F_{n}}^2 + 41$$ is always a composite number. It looks that if $n$ is not multiple of 12, ${F_{n}}^2 + 41$ ...
2
votes
1answer
95 views

A question on prime density

Let A = {c > 1 : there exists a natural number m, such that for every n > m, there is a prime between n and cn}. Bertrand's postulate says that A contains 2. My question is : Is inf A = 1 ? If not, ...
2
votes
2answers
460 views

Confusion on the proof that there are “arbitrarily large gaps between successive primes”

I am trying to wrap my brain around a proof that proves that there are arbitrarily large gaps between successive primes. The proof is Given a natural number $N\ge2$, consider the sequence of $N$ ...
2
votes
2answers
236 views

How many prime number factors are there for 420(base 6)?

I don't know the actual approach. I did it this way: $2\cdot210=420$ (base 6) $2\cdot103=210$ (base 6) $3\cdot21=103\;$ (base 6) Now $21$ (base 6) $= 13$ (base 10) = prime So, the total number of ...
14
votes
1answer
440 views

German sofa primes: Can both $q$ and $\frac{q^3+1}{2}$ be prime?

Is there an odd prime integer $\displaystyle q$ such that $\displaystyle p= \frac{q^3+1}{2}$ is also prime? A quick search did not find any, nor a pattern in the prime factorization of p. This ...
3
votes
1answer
69 views

Efficiently doing prime factorisation by hand

I have a yes/no question first (if 2 questions are allowed in 1 post). When doing prime factorisation for using the Euler totient function can you use a particular prime more than once. (i.e. $p_{1} ...
2
votes
1answer
67 views

For every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

Prove that for every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$. I have no idea how to prove that.
37
votes
5answers
6k views

If a prime number is reversed, and then appended to itself, why is the result always a composite number?

$2 \Rightarrow 22$ which is a composite number. $37 \Rightarrow 3773$ which is a composite number. $523 \Rightarrow 523325$ which is a composite number. $8123 \Rightarrow 81233218$ which is a ...
3
votes
2answers
242 views

find x where $x^{11} \mod 41 = 10$

In a previous part of the question, I am asked to find $11^{-1} \mod 40$. I've done that, the answer's $11$. The question continues: find $x$ where $x^{11} \mod 41 = 10$ showing how you could get ...
2
votes
1answer
74 views

Question about $2p-1$ and $2p+1$, where $p$ is a prime.

Let $x+1$ be any prime greater than $3$. By Bertrand's Postulate, there is at least one prime between $\frac{x}{2}$ and $x$. Let $\{p_1,p_2,\dots, p_n\}$ be the primes between $\frac{x}{2}$ and ...
2
votes
1answer
279 views

Is this infinite series related to prime and composite numbers convergent?

I don't know whether this series converges: $$(\frac{1}{4} - \frac{1}{5}) + (\frac{1}{6} - \frac{1}{7}) + (\frac{1}{8} + \frac{1}{9} + \frac{1}{10} - \frac{3}{11}) + (\frac{1}{12} - \frac{1}{13}) + ...
17
votes
1answer
264 views

The n-th prime is less than $n^2$?

Let $p_n$ be the n-th prime number, e.g. $p_1=2,p_2=3,p_3=5$. How do I show that for all $n>1$, $p_n<n^2$?
10
votes
5answers
996 views

Are numbers of the form $n^2+n+17$ always prime

Someone claimed that a number, multiplied by the number after it plus 17 is always prime, and showed several cases. I'm not a complete amateur in Number Theory, and I know that $17*18+17=17*19$, so it ...
0
votes
1answer
371 views

Why does the number of divisors of a superior highly composite number is always a highly composite number up to 720720 ? (the only exception is 120)

I've calculated the number of divisors of every superior highly composite number up to $10^{27}$: The number of divisors of a superior highly composite number is always a highly composite number up ...
1
vote
1answer
44 views

big $\mathcal O$ for number of prime in an interval?

According to von Koch 1991, if the Riemann hypothesis is true, then the for the prime counting function $$\pi(x)=Li(x)+\mathcal O(\sqrt x \log x)$$ I am trying to understand how to deal with the ...
2
votes
0answers
111 views

Riemann's explicit formula for $\pi(x)$

Riemann's explicit formula $J(x)=\mathrm{Li}(x)-\sum_{\Im\varrho>0}\left(\mathrm{Li}(x^\varrho)+\mathrm{Li}(x^{1-\varrho})\right)+\int_x^\infty\frac{\mathrm{d}t}{t(t^2-1)\log t}-\log2,$ where ...
1
vote
0answers
102 views

Primality of Stirling numbers of second kind (again)

This question follows a previous one on the primality of Stirling numbers of the second kind ${n \brace k}$. Gerry indicated a paper on the topic. In this paper it is shown that for ${n \brace k}$ to ...
1
vote
2answers
225 views

Distinct Mersenne numbers are coprime

How can you prove that if $p$ and $q$ are distinct primes, then the following holds?: $$(M_p,M_q)=1$$ Note: $M_n=2^n-1$, with $n$ prime number
3
votes
1answer
78 views

Showing irrationality of $\zeta(k)$ for some $k$ without calculating the value.

For $s\in (1,\infty)$ let $\zeta(s):=\sum_{n=1}^\infty \dfrac 1{n^s}$. Is there a way to show that $\zeta(2k)$ is irrational for some integer $k\geq 1$ without finding explicit formulae?
1
vote
1answer
26 views

Show T being prime element in $ F_{2}(T) $

Show that $X^4+TX^2+T$ is irreducible in $ F_{2}(T) $ Using Eisenstein with T as a prime element this proof is simple. Can I proof that T is prime any easier than in the folowing: Theorem 1: K is ...
1
vote
3answers
206 views

Showing that a composite number has a small prime divisor?

At the moment I'm working on proving some statements and I've run into one that I can't seem to wrap my head around. It goes like this: For $n \in \mathbb{Z}^+$, we define $\sqrt{n}$ as the real ...
4
votes
0answers
107 views

More on primes $p=u^2+27v^2$ and roots of unity

Given, $$p=u^2+27v^2=3m+1\tag1$$ and the cubic, $$x^3+x^2-mx+N=0\tag2$$ with its constant expressed in terms of $(1)$ as, $$N = \frac{1}{27}(1-3p\pm2pu)\tag3$$ and the sign $\pm u$ chosen ...
6
votes
1answer
106 views

What is the least number $n$, such that $n^{2015}+2015$ is prime?

What is the least number $n$, such that $n^{2015}+2015$ is prime ? According to my calculations, there is no prime for $n\le 6000$. It is clear, that $n$ must be even, since $n^{2015}+2015$ must be ...
0
votes
0answers
42 views

questions about probabilistic primality test

As usual I used online Miller-Rabin test,but there's one thing that i don't understand: when i tested 2500 digit or so numbers it only took 1 or few minutes,but there was few numbers that took an ...
5
votes
5answers
2k views

Prime number between $n$ and $n!+1$

I am trying to prove that ($\forall \ n\in\mathbb{N}$) there exists a prime number $q$ such that $n < q \le 1 + n!$ I have made a graph with $n=0$ through $n=10$ and found solutions to all of them ...
1
vote
2answers
74 views

Clarification regarding Prime theorem

This is one theorem which I came across the book: For every positive integer $n$, there is a sequence of $n$ consecutive positive integers containing no primes. Is this theorem valid ? Because ...
42
votes
3answers
49k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
4
votes
0answers
53 views

Not using Jacobi symbol how to prove For all positive integer $n>1$ $2^n - 1 \not | 3^n-1$?

There is a proof: if $n$ is even,then $3|2^n-1$ but $3\not|\;3^n-1$,It is correct; if $n$ is odd,suppose $2^n-1|3^n-1$,then $3^n \equiv 1(\mod 2^n-1)$,then ...
0
votes
0answers
40 views

let $G$ to be group such that $O(G)=p^2$ where $p$ is prime,prove that $G$ is cyclic or $G$ is Direct product of two cyclic subgrops of order $n$. [duplicate]

the only hint that i got is Sylow's first theorem, which implies that if $p^n$ is any prime power dividing $O(G)$, then $G$ has a subgroup of order $p^n$. in our case $p$ devides $p^2$, then we can ...
3
votes
1answer
219 views

Cramer and Riemann Conjecture Implication

Cramer's conjecture gives $$p_{n+1}-p_n= O(\log^2 p_n)$$ while Riemann Hypothesis yields just $$p_{n+1}-p_n= O(\sqrt p_n\log^2 p_n).$$ Does Cramer conjecture on prime gaps imply Riemann Hypothesis ...
2
votes
1answer
62 views

Finding partitions $\{A,B\}$ of the set $\mathbb N_n:=\{1,…,n\}$ such that $\Big|\prod_{i \in A}p_i-\prod_{i\in B}p_i\Big|=1$

For a fixed $n$ , for what partitions $\{A,B\}$ of the set $\mathbb N_n:=\{1,...,n\}$ do we have $\Big|\prod_{i \in A}p_i-\prod_{i\in B}p_i\Big|=1$ ? , where $p_m$ denotes the $m$th prime for ...
3
votes
2answers
218 views

Solving an equation for two primes

This is from contest preparation: Find all pairs of primes $(p, q)$ that satisfy $$p^q - q^p = p q^2 - 19$$. It looks simple, but I spent hours trying to solve it... and no luck so far. ...
9
votes
0answers
368 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
0
votes
3answers
62 views

What is the product of $p_i-1 \over p_i$ [duplicate]

I am trying to find the value of $\prod_{i=0}^{\infty}{p_i-1 \over p_i}$ = ${\lim_{x \to \infty}} {\phi(p_x!) \over p_x!}$ Where $p_x!$ is the $x$th primorial, and $p_i$ is the $i$th prime number. I ...
0
votes
0answers
276 views

What is the next such prime

This is about primes with "very" interesting forms. Such this one: primes $p$ such that the concatenation of first $k$ primes with only prime digits (i.e. $2$, $3$, $5$ and $7$) from $2$ to $p$ is a ...
8
votes
1answer
246 views

What's so special about primes $x^2+27y^2 = 31,43, 109, 157,\dots$ for cubics?

While trying to find a closed-form solution for particular cubics as sums of cosines (related to this question), I came across this family with all roots real, $$F(x) = x^3+x^2-mx+N = ...
2
votes
1answer
651 views

If the order divides a prime P then the order is P (or 1)

I've just come up with this question as I'm studying for a number theory midterm. If $p$ and $q$ are different prime numbers, and it's known that $2^p \equiv 1 \bmod{q}$, then $q\equiv 1 \bmod{p}$. ...