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

13
votes
2answers
689 views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any ...
19
votes
2answers
312 views

The Gaussian moat problem and its extension to other rings in $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$

One of my favourite open problems in number theory, an area in which I enjoy only as a hobbyist, is the Gaussian moat problem, namely "Is it possible to walk to infinity in $\mathbb{C}$, taking ...
0
votes
1answer
33 views

Field Characteristic Is Prime…?

Consider the article: http://mathworld.wolfram.com/FieldCharacteristic.html It is stated that given a field and its multiplicative identity $I_{\times}$ that either: $$ \sum_{i=0}^{k}{I_{\times}} ...
0
votes
1answer
51 views

Is it true that in $2^n-1$, when $n$ is a prime number, you don't always get a Mersenne prime?

For $2^n-1$, where $n$ is a prime number, is it true that you don't always get a Mersenne prime? Remember, a Mersenne prime is a number that has a power of two subtracted by one and is then ...
0
votes
1answer
60 views

Reduced residue systems and prime k-tuple bijection

First off, the terminology: Primorials: the products of the first $n$ primes, written as $P_n \#$. Reduced residue system modulo a positive integer $K$: Those numbers smaller than $K$ that are ...
0
votes
1answer
45 views

Question about Euclid's infinite prime proof

Suppose that $p_1=2 < p_2 = 3 < \cdots < p_r$ are all of the primes. Let $P = p_1p_2...p_r+1$ and let $p_s$ be a prime dividing $P$ where $p_s$ is not in our original list $p_1, p_2, \cdots, ...
10
votes
4answers
2k views

Why are all non-prime numbers divisible by a prime number?

In Euclid's infinite prime numbers proof, the logic is as follows: Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes) Then there must be a greatest ...
1
vote
1answer
44 views

Is there any $k$ such that there are no primes with $k$ digits?

It seems that for any base $b\geq 2$, and for any number of digits $k\geq 2$, there is always some prime number that is $k$ digits long in base $b$. For example, in base $10$, for $2\leq k\leq 10$ we ...
0
votes
2answers
95 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
22 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
1k 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 ...
6
votes
1answer
220 views

Prime Number Sieve using LCM Function

How to prove following conjecture ? Definition : Let $b_n=b_{n-2}+\operatorname{lcm}(n-1 , b_{n-2})$ with $b_1=2$ , $b_2=2$ and $n>2$ . Let $a_n=b_{n+2}/b_n-1$ Conjecture : Every term of ...
0
votes
2answers
54 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 ...
1
vote
0answers
53 views

Fermat Primes re edited [duplicate]

First of all sorry for sending the same question. Is my cited below observations are true? If yes, how to prove? 1) Many of $poulet$ numbers are in the form of $(4^x -1)$/$3$, where $x$ is some ...
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 ...
14
votes
3answers
533 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 ...
31
votes
2answers
7k views

Yitang Zhang: Prime Gaps

Has anybody read Yitang Zhang's paper on prime gaps? Wired reports "$70$ million" at most, but I was wondering if the number was actually more specific. *EDIT*$^1$: Are there any experts here who ...
7
votes
2answers
114 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
185 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 ...
1
vote
1answer
29 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 ...
15
votes
1answer
229 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
60 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 ...
0
votes
3answers
46 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 ...
2
votes
0answers
47 views

Find the integral values for which $\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$

Let $\pi(x)$ be the prime counting function. Find all integral values of $x,y$ such that, $$\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$$ I have no idea as to where to begin with. I think that probably ...
6
votes
1answer
95 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 ...
6
votes
1answer
105 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$ ...
-1
votes
0answers
22 views

Consequences of Cramer's conjecture being false

What if there is an $n_0\in\Bbb N$ such that at almost every $n>n_0$, $$p_{n+1}-p_n=\Omega(p^a)$$ holds with some fixed $a>0$. What are some consequences of this statement in number theory?
1
vote
1answer
80 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
78 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
89 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
427 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
53 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} ...
3
votes
1answer
58 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.
34
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
187 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 ...
3
votes
1answer
68 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 ...
0
votes
0answers
16 views

Estimates for a Mertens-type Product.

The first corollary of Theorem 8 of this paper by Rosser and Schoenfeld states that $$\prod_{p\leq x}\left(\frac{p}{p-1}\right)<e^{\gamma}(\log x)\left(1+\frac{1}{\log^2 x}\right)$$ for all $x\geq ...
1
vote
2answers
63 views

Is a prime to the power of a fraction always irrational?

Let $p$ be a prime number and let $x$ be a faction, i.e. $x \in \mathbb{Q} - \mathbb{N}$. It seems to be the case that $p^x$ is always irrational. How do I prove this?
2
votes
1answer
241 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}) + ...
15
votes
1answer
177 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
367 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
165 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 ...
47
votes
8answers
6k views

The myth of no prime formula?

Terence Tao claims: For instance, we have an exact formula for the $n^\text{th}$ square number – it is $n^2$ – but we do not have a (useful) exact formula for the $n^\text{th}$ ...
0
votes
1answer
33 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 ...
1
vote
0answers
56 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
73 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
111 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
74 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?
0
votes
1answer
21 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 ...
2
votes
3answers
89 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 ...