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

1
vote
2answers
59 views

A polynomial formula for the primes

Is there a proof that there is no polynomial which would return $n$th prime for the input value $n$? In other words is there an explanation for why there is no polynomial $P(x)$ such that $P(n)=p_n$ ...
16
votes
2answers
2k views

Math Olympiad Prime Number Question

If $p$, $q$ and $r$ are prime numbers such that their product is $19$ times their sum, find $p^2$ + $q^2$ + $r^2$. I came across this question in a Math Olympiad Competition and had no idea how ...
6
votes
3answers
134 views

Primes as a difference of powers

Find the smallest prime that cannot be written as $$|3^a - 2^b|$$ EDIT: I forgot to mention that $a$ and $b$ are whole numbers. I tried to expand $3^a$ as $(2+1)^a$ using binomial theorem but ...
2
votes
3answers
62 views

How to use Legendre symbol to find a prime which divides $ax^2+b$?

I'm trying to prove that $\dfrac{x^2-2}{2y^2+3}$is never an integer if $x,y\in\mathbb{Z}$. It can be proven if $\forall p\in\mathbb{P}\:$doesn't suffice both of the following congruences: $$\: ...
2
votes
2answers
106 views

Prove that $a^n+b^n \equiv (a+b)^n \mod n$, if $n$ is prime and $a,b$ are integers.

What is the best method to prove that if $n$ is prime and $a,b$ are integers $a^n+b^n \equiv (a+b)^n \mod n$, ?
1
vote
0answers
34 views

What is the status of research on primes as an example of general sieve-generated sequences?

I have been interested in treating the prime numbers as a special case of sieve-generated sequences, however they may be defined by different authors. Can someone here give me any information about ...
1
vote
2answers
34 views

Upper bound for the difference between number-of-divisors and sum-of-divisors functions

The number-of-divisors function $d$, and the sum-of-divisors function $\sigma$, are defined by $$ d(n) = \sum_{d \mid n} 1, $$ $$ \sigma(n) = \sum_{d \mid n} d, $$ respectively. Now let $N$ be a ...
9
votes
5answers
215 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 ...
1
vote
1answer
20 views

Examine if $\exists M$ such that $\forall n>M$, $\pi(2n)$ $-$ $\pi(c_n)$ $>$ $0$

The problem is- Examine if $\exists M$ such that $\forall n>M$, $\pi(2n)$ $-$ $\pi(c_n)$ $>$ $0$. Also find a value of such $M$ for which the theorem is true. Though I haven't still given ...
1
vote
2answers
41 views

prove that $N$ is divisible by $1,2,\ldots,k$ which $k+1$ is the lowest prime number after $N$

Suppose $n$ is a natural number ($n\ge 5$) and $k+1$ is the lowest prime number that is greater than $n$ prove that $A_i \mid n!$ which $A_i$ are these numbers: $1,2,\ldots,k$
3
votes
1answer
28 views

Is ${(prime^2-1) \over 24}$ always a member of the generalized pentagonal number set?

I was working through a puzzle on why the square of a prime minus one is always a factor of 24 (http://puzzles.nigelcoldwell.co.uk/fifteen.htm) and noticed that the sequence of numbers for ...
5
votes
2answers
330 views

Proof that no polynomial with integer coefficients can only produce primes

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but ...
1
vote
1answer
75 views

Are there Generalizations of this theorem I found on a chit of paper?

Some time ago , I was reading a book which was not of a mathematical taste from a library . But from that book a chit of paper came out which was handwritten and had the title : Aubry's theorem And it ...
4
votes
1answer
64 views

Question about the proportions of primes p for which $ord_p(2)$ satisfies certain congruences

let $p$ be a prime. I have observed numerically that the proportion of $p$ satisfying $ord_p(2)\equiv4[8]$ seems to be $1/3$. Why is it so? Is there a simple proof? Moreover the proportion $c$ of ...
0
votes
1answer
76 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}$: http://oi59.tinypic.com/ndaijo.jpg The number of divisors of a superior highly composite number is ...
1
vote
1answer
130 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
12
votes
3answers
409 views

Number Theory or Algebra?

Prove that if $4^m-2^m+1$ is a prime number, then all the prime divisors of $m$ are smaller than $5$ I initially thought about putting $4^m-2^m+1=p$ where $p$ is some prime and after eliminating ...
0
votes
1answer
28 views

$\psi(p_{n+1}) - \psi(p_n)$?

Let $$S(p_n)=\psi(p_{n+1}) - \psi(p_n)$$ where $p_n$ is the $n$-th prime, and $\psi(x)$ second Chebyshev function. With $u=\log(x)/\log(2)$, This the same as, with the first Chebyshev function ...
2
votes
1answer
32 views

Is a Lucas Number with either a power of 2 or a prime index always coprime with all previous Lucas Numbers?

I was looking at this webpage which lists the first 200 Lucas Numbers color-coded with their prime factors and I noticed that all the Lucas numbers with power of two or prime indexes were relatively ...
15
votes
1answer
157 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 ...
1
vote
1answer
63 views

Prime or composite?

Factorials are very interesting to solve. How will you find that $2014!+1$ (where '$!$' means factorial) is prime or composite ?
0
votes
1answer
102 views

Are there composite numbers matching the conditions?

Conditions: n such that $\ Ord_n(2) \mid n-1 $ and $\ Ord_n(2) - 1 = 2^x,n \in >2\mathbb{N}+1,\ x \in \mathbb{Z}_{\geq 0}$. I check up to 1e7 : ...
1
vote
1answer
40 views

Prime triplets and congruences

Show that if $n$, $n+2$ and $n+6$ are a prime triplet then $4320(4((n-1)!+1)+n)+361n(n+2)\equiv0\ \pmod{ (n(n+2)(n+6)}.$
3
votes
0answers
90 views

Sum of product partitions of divisors

Let $M(n)$ be the the set of the multiplicative partitions of $n$, and let $D(n)$ be the set of the sum of the multiplicative partitions of the divisors of $n$. eg $M(30)=\{\{30\},\{2,15\},\{3, ...
1
vote
0answers
28 views

Is there a Poulet number with this condition?

Is there a Poulet number $n$ with this condition: $◎(n)=\frac{n+1}{2^x}$ or $\ ◎(n)=\frac{n-1}{2^x}, \ x \in \mathbb{N}_{\gt 0}$? (Recall that a Poulet number is a composite $n$ such that $2^n−2$ is ...
1
vote
1answer
70 views

Prove or disprove that $\forall k\in\mathbb N$ there exist tree consecutive primes such that $p_i-p_{i-1}\gt k$ and $p_{i+1}-p_{i}\gt k$

Prove or disprove that for every positive integer $k$, there exist tree consecutive primes $p_{i-1}, p_i, p_{i+1}$ such that $p_i-p_{i-1}\gt k$ and $p_{i+1}-p_{i}\gt k$. It's well known that ...
3
votes
1answer
29 views

Group of numbers in residue number system of first $n$ primes

Denote $$\Pi_n = \Pi_{i=1}^n p_i$$ ie. the product of the first $n$ primes. Assume we have a number $m$. Denote $$L(m) = k \iff \Pi_{k-1} < m \le \Pi_{k}.$$ Assume also $L(1)=1.$ Now, if $L(m) = ...
0
votes
0answers
12 views

Connes trace doubt and operator $ H=xp$

i am trying to understand the paper from page 315 and on http://www.alainconnes.org/docs/bookwebfinal.pdf a) in the form of a sum of primes what does the integral $$ \int _{Q_{p}} ...
0
votes
1answer
29 views

Prove that there is no such positive rational pair and positive odd prime, for which $q_1^p+q_2^p=1$ [closed]

Prove that there is no pair of positive rational numbers $q_1,q_2\in\Bbb{Q}^2$ and positive odd prime $p$, for which $q_1^p+q_2^p=1$
0
votes
0answers
48 views

For all prime $\ p > \ 2,\ p=2^x \cdot Ord_p(2)+1$?

For all prime $\ p\ > \ 2,\ p=2^x \cdot Ord_p(2)+1?\ $ Where $\ x \in \mathbb{Z}_{\geq 0}.\ $ Such as $\ Ord_3 (2) = 2, \ 3=2^0 \cdot 2 + 1$. Is there some way to prove this?
0
votes
1answer
32 views

Cut a piece of dough into $3$ even pieces

How could you cut a piece of dough into $3$ even pieces? Cutting it into $2$ is easy, but it's not that trivial for greater numbers. If you can cut it into $n$ pieces, you could repeat the process on ...
2
votes
1answer
29 views

Given $N$ is the product of $m$ distinct primes, how many $K(K+1)$ are divisible by $N$?

Let $N$ be the product of two distinct primes $P_1$ and $P_2$. Let $S$ be a set of all $K<N$, such that $N|K(K+1)$. For example, if $N$ is $5\cdot7=35$ then $S=\{14,20\}$. The size of $S$ in ...
2
votes
0answers
33 views

Subfactorial primes

So I just did some stuff and from what I can see, if y > x then !x + !y can only be prime if y = x+1 (apart from a few small exceptions near the start of the list. I don't know anything about ...
3
votes
1answer
305 views

the sum of ascending powers of a prime can not equal the sum of ascending powers of a different prime.

I was thinking about a question that I can't prove and can't find any proof/counter example for so here it is: prove the equation: $$ \sum\limits_{i=0}^x p_1^i = \sum\limits_{i=o}^y p_2^i $$ has no ...
0
votes
0answers
30 views

Has anyone used the isomorphism with $\Bbb{N}_{\gt 0}$ as a monomial ordering?

Let $R[x_1, x_2, \dots]$ be a ring of formal polynomials in a countably $\infty$ number of indeterminates $x_i$, over a commutative ring $R$. The commutative monoid $X = \{ x^e = x_1^{e_1} x_2^{e_2} ...
2
votes
1answer
99 views

Is there a known function $f(n) = P_n$, where $P_n$ denotes the $n$th prime number?

Is there a known function $f:\mathbb{R}\to\mathbb{R}$, such that: The definition of $f$ does not contain the $!$ operator The definition of $f$ does not contain the $\sum$ operator The definition of ...
4
votes
2answers
79 views

Compute $ \lim_{n\to \infty}\prod_{i=1}^n B(p_i^{-2})$

Let $B(x) = \begin{pmatrix} 1 & x \\x & 1 \end{pmatrix}$, and $2=p_1<p_2<\cdots <p_n <\cdots$ primes number. Compute $$\displaystyle \lim_{n\to \infty}\prod_{i=1}^n ...
6
votes
1answer
116 views

Prime Number Theorem and sum of reciprocals of primes

This is not a homework problem. I am a mathematician (group representations and classical analysis) who never studied number theory and am beginning with Niven’s book. My question concerns the ...
2
votes
1answer
34 views

Prove that there are an infinity of prime $ak+b$, $a$ and $b$ coprimes

We have to integers $a,b$. I need to show that if $a$ and $b$ are coprimes then the set of prime numbers of kind $ak+b$ is infinite. How could I show it ? I know how to do that for $4k+3$ or $4k+1$, ...
2
votes
3answers
101 views

Smallest Prime Factor - Why does this algorithm find prime numbers?

I have been looking at the problems on Project Euler and a number of them have required me to be able to find the prime factorisation of a given number. While looking for quick ways to do this, I ...
1
vote
1answer
33 views

Algorithm for checking Prime Power

Suppose we are given some arbitrary positive integer. How can we check whether the integer is a prime power? Brute force would be very inefficient in this case.
1
vote
2answers
75 views

Is it sufficient for a number to be a prime if it is not divisible by prime numbers smaller than it?

I am student of computer science with no knowledge of maths. To write a small algorithm I searched for the solution first. There are many but almost all of them state that continue dividing the number ...
2
votes
2answers
57 views

Does there exist any integer $ n> 1$ for which $6^{2n}-25$ is prime?

I got this question on a test and I am really curious hoe you would approach it. I tried to prove stuff using the congruence laws but I didn't manage to prove anything.
1
vote
1answer
126 views

Is my conjecture true? : Every primorial is a superior highly regular number, and every superior highly regular number is a primorial.

I have invented two sets of positive integers: highly regular numbers and superior highly regular numbers. A positive integer $m \leq n$ is a regular of the positive integer $n$ if all prime numbers ...
2
votes
1answer
62 views

Show that $\mathbb{Q}(\zeta)$ contains one of the two numbers $\sqrt{\pm5}$ and decide which one is contained in $\mathbb{Q}(\zeta)$.

Let $\zeta$ be the 15th primitive root of unity in $\mathbb{C}$, show that $\mathbb{Q}(\zeta)$ contains one of the two numbers $\sqrt{\pm5}$ and decide which one is contained in $\mathbb{Q}(\zeta)$. ...
1
vote
1answer
31 views

Is my proof correct regarding the non primality of $2\cdot 17^a +1$?

Today I need your help to know if the proof I have provided below is correct or not. I want to prove that there is no prime of the form $2\cdot 17^a+1$ where $a\in \mathbb N$. Now, first of all, I ...
10
votes
5answers
920 views

Decimal form of irrational numbers

In the decimal form of an irrational number like: $$\pi=3.141592653589\ldots$$ Do we have all the numbers from $0$ to $9$. I verified $\pi$ and all the numbers are there. Is this true in general for ...
0
votes
1answer
29 views

How to prove if an arithmetic function is multiplicative?

I know that for an arithmetic function to be multiplicative then $f(nm)=f(n)f(m)$ for $(n,m)=1$ I have just proved that: $$f(n) = \left\{ \begin{array}{l l} 0 & \quad \text{if 10|n}\\ ...
0
votes
2answers
73 views

if N is the Sum of P primes, computer program homework [closed]

Given a natural number $N$ and a positive integer $P$. I need to write a computer program that outputs if $N$ can be represented as a sum of $P$ prime numbers which need not be distinct. We need to ...
3
votes
1answer
69 views

Existence of a prime partition

I'm interested in finding out whether there exists a prime partition of a given positive integer $N>1$ such that the partition has specific number of parts. For instance, as given in another ...