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

0
votes
0answers
11 views

What can we say about $\frac{s}{p}$, $\frac{p}{s}$ using these 3 imposed conditions?

What can we say (if anything) about $\frac{s}{p}$ or $\frac{p}{s}$ where $p$ and $s$ are integers greater than $1$ using the following three conditions: $p>s$, $s$ and $p$ are not both divisible ...
2
votes
1answer
1k views

Infinitely many primes $\equiv 2 \pmod 3$ proof correctness

I know I have already asked a question regarding this proof. However, I wanted to see if my reformulation of this proof (with my better understanding in my own words and after some time) is correct. ...
5
votes
3answers
3k views

Can Prime numbers be negative?

I was wondering, can a prime number be negative? We had a question over at security.se which stated that prime generation with openssl: openssl dhparam -text 1024 ...
0
votes
2answers
42 views

Odd Primes Problem Proof

Given the odd prime numbers, Prove that if $x$ and $y$ are adjacent odd primes in this list, then $x + y$ has $3$ prime factors. The factors need not be distinct. Here is an example I have ...
4
votes
2answers
101 views

Show that $p!$ and $(p - 1)! - 1$ are relatively prime

If $p$ is prime number, with $p>3$ Show that $p!$ and $(p - 1)! - 1$ are relatively prime. I tried $\text{gcd}\;(p!,(p-1)!-1)=d\Longrightarrow d\mid p!$ e $d\mid(p-1)!-1$ having ...
2
votes
1answer
32 views

How can one show that $\prod_{n<p\leq2n}p\leq C(2n,n)$?

I am trying to rove that $\prod_{n<p\leq2n}p \leq C(2n,n) \leq 2^{2n}$, where $C(2n,n)= \frac{2n!}{n! n!}$ and $p$ is prime. I can prove the second part by induction, but first part induction ...
7
votes
4answers
191 views

$5^{2012}+1$ is divisible with $313$

Prove that: $\displaystyle5^{2012}+1$ is divisible with $313$. What I try and what I know: $313$ is prime and I try use the following formula : ...
2
votes
2answers
93 views

Perfect divisibility for products in modular arithmetic

Say we have that $z^2 - x^2 = 0 \ ( \ mod \ p)$ that implies: $p \ | \ (z-x)(z+x)$ However I was not 100% sure how that implies about the divisibility of p towards $(z-x)$ and/or $(z+x)$ and ...
36
votes
3answers
3k views

Is $n! + 1$ often a prime?

Related to this question, I wonder how often $n!+1$ is a prime? There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not... or anything in that sense...
1
vote
3answers
79 views

If $p \mid a^n$ then does $p^n \mid a^n$? [duplicate]

I'm trying to figure out if the statement is true or not and I need to prove it if so. Let $p$ be a prime and $a$ be an integer. If $p\mid a^n$ , is it true that $p^n\mid a^n$ ? I'm not sure how i ...
0
votes
0answers
28 views

proving prime number's divisors

Let p ̸= 0, ±1 be an integer. Prove that p is prime if and only if p satisfies the following property: Whenever a and b are integers such that p = a · b, either a = ±1 or b = ±1. I proved the forward ...
13
votes
2answers
686 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
308 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
94 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
20 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
219 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
53 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
6k 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
228 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
59 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
46 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
20 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
88 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
52 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
15 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
2answers
115 views

prime factors of number with a particular form

I try to factorize this huge number $2^{(3^{(5^7)})} +7^{(5^{(3^2)})}$ .but i have no idea,the only thing i know is that it's not divisible by 7 and 11. can you help me find some prime factors of ...