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
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 ...
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?
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, ...
32
votes
5answers
652 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$ $${F_{n}}^2 - 28$$ cannot be a prime. I came to this accidentally while trying to solve another ...
-3
votes
0answers
33 views

why are prime numbers important to us today? [duplicate]

Need this for homework. It would be a big help, thanks. I tried the questions some other people posted but they don't have the answer I want.
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 ...
6
votes
1answer
93 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
28 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 ...
2
votes
2answers
59 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 ...
2
votes
2answers
123 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 ...
0
votes
0answers
32 views

On $p^{\log_q n}$, where $p$ and $q$ are distinct primes

Let $p,q$ be distinct primes, $n>1$ an integer with $\log_q n $ irrational. It was, and probably still is, a conjecture that $p^{\log_q n}$ is non-integer. What progress has been made towards it?
0
votes
0answers
38 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 ...
4
votes
0answers
50 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 ...
1
vote
1answer
45 views

On the prime number theorem in shorts intervals

In 1988 Heath-Brown (" The number of primes in a short interval ", J. reine angew. Math. 389, 22-63) proved this theorem: Let $\varepsilon\left(x\right)\leq\frac{1}{12}$ be a non-negative function ...
3
votes
1answer
91 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 ...
0
votes
3answers
28 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 ...
1
vote
0answers
262 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 ...
3
votes
2answers
189 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. ...
4
votes
0answers
78 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 ...
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} ...
1
vote
2answers
45 views

$p_n<n\left(\log n + \log\log n\right)$

Wikipedia told me this bound (which of course holds true if $n\ge6$) for the $n$-th prime is due to Bach and Shallit, and I found "Eric Bach and Jeffrey Shallit: Algorithmic Number Theory, Volume I: ...
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 ...
1
vote
2answers
38 views

Probability of a subset of the first $n$ natural numbers are prime.

Suppose we have $P(x) = \frac{1}{n}$ for $x \in \{1,...,n\}.$ Is there a way to find out what the probability is for $P(A_p)$ where $A_p$ is the set of integers $x\in \{1,...,n\}$ such that $x$ is ...
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 ...
5
votes
3answers
177 views

For all $n>2$ there exists a prime number between $n$ and $ n!$

How to prove that there exists a prime number between $n$ and $ n!$, for all $ n> 2$? (Bertrand's postulate gives a much better bound, but this question is about obtaining a self-contained ...
1
vote
0answers
31 views

On integer $n>1$ and prime $p$ such that $p<n$ , $p$ does not divide $n$ and $n-p$ is a prime

Let $n>1$ be a given integer and $p$ be a prime less than $n$ and not dividing $n$ ; so $p$ and $n$ are co-prime ; hence $n-p$ and $n$ are also co-prime ; I would like to ask when is $n-p$ also is ...
2
votes
1answer
86 views

two questions about primes

I'm very ignorant about results in number theory concerning the primes. Please let me know if these are open conjectures or easy problems: There are infinitely many primes of the form $n!+1$ There ...
2
votes
1answer
50 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 ...
1
vote
1answer
29 views

Hamming (5-smooth) numbers

Until quite recently, I was not aware of the idea of "smooth" numbers. This is perhaps better expressed as "N-smooth" numbers (i.e., integers where the largest prime factor is <= N). 5-smooth ...
5
votes
3answers
134 views

Proving the following false: $f(x)=2x+1$ produces a prime number if and only if x is prime

$f(x)=2x+1$ produces a prime number if and only if x is prime, how can we prove this false? I know this isn't very math-proofy, but can't we just plug in a number we know that is prime, i.e. $x=7$, ...
2
votes
2answers
72 views

Chebyshev's first function prime count

How is Chebyshev's first function $$\vartheta(N)=\sum_{p\leq N}\log p$$ useful in counting primes? Can it alone be used to analytically derive the prime number theorem?
5
votes
0answers
48 views

More primes of the form $6k-1$ than $6k+1$

Let $a_n:= $ number of primes of the form $6k-1$ and $\le n$ and $b_n:= $ number of primes of the form $6k+1$ and $\le n$. I was playing with my computer and noticed that $a_n\ge b_n$ for ...
1
vote
1answer
51 views

Natural Number Generator

Motivated with this question I formulated following question : Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers where $p$ is a prime number of the form $4k+3$ ? I wrote Maxima ...
1
vote
1answer
32 views

The alternating sum of primes defines an injection

Define $\displaystyle\alpha(n)=\sum^n_{k=1}(-1)^{n-k}p_k$, where $p_k$ is the $k$:th prime. Show that $\alpha$ is an injection $\mathbb Z_+\to\mathbb Z_+$. It's easy to see while considering sums as ...
19
votes
6answers
1k views

Digit sequence that is not prime in any base

Is there a sequence of base-$b$ digits of length greater than one with all digits $\ne 0$ that does not represent a prime number in any base? Example: $12_{10}=12$ is not prime, but $12_3=5$ is.
4
votes
2answers
171 views

Find all the prime numbers that satisfy the following conditions

There was a brainteaser in the Science Magazine from University of Hong Kong which is as follow: Find all the prime numbers $p$ such that $\sqrt{\frac{p+7}{9p-1}}$ is rational. I tried a few numbers ...
0
votes
1answer
41 views

How many primes can be represented in JavaScript?

In JavaScript, the largest odd positive number representable is $2^{53}-1$. All integers between 1 and $2^{53}-1$ can be represented without loss of precision. How many prime numbers can be ...
2
votes
1answer
66 views

Some questions about prime divisors and number of primes

For an integer $n \ge 2$, let $\omega (n)$ denote the number of distinct prime divisors of $n$ and $\pi (n) $ be number of primes not exceeding $n$. Let $a_1, \ldots, a_k$ be integers greater than ...
4
votes
1answer
172 views

Determining the starting value for primality test

This question is about Lucasian primality test for numbers of the form $N=3\cdot 2^n-1$ . There is a following statement in Wikipedia article : Lucas-Lehmer-Riesel test : "If $k = 3$ : if $n = 0$ ...
1
vote
2answers
67 views

Does $p_{1}^x + p_{2}^y = n$ have uniqe solution for $x$ and $y$ ($p_{1}, p_{2}$ are primes).

If I'm given a value $n$. And I know its of the form $p_{1}^x + p_{2}^y$, can I be sure that there is a unique solution for $x$ and $y$ and Can I determine values of $x$ and $y$, If I know the ...
0
votes
2answers
107 views

Why $1$ isn't a prime? [duplicate]

I was wondering the reason behind defining the Prime Numbers in a manner of which $1$ isn't an example. I read in Rotman's A First Course in Abstract Algebra that one reason that $1$ is not called a ...
11
votes
1answer
67 views

Divisors of sequence $n,P(n),P(P(n)),\ldots$

Let $P(x)$ be a polynomial with nonnegative integer coefficients consisting of more than one nonzero term. Let $n$ be a positive integer. Is the set of prime numbers which divide at least one number ...
2
votes
3answers
58 views

Is there a number congruent to 1 modulo infinitely many primes?

Let $A=\left\{ p_{r},p_{r+1},\dots\right\}$ a (infinte) set of consecutive prime numbers (if you prefer, if $\mathfrak{P}$ is the set of all prime numbers, $A=\mathfrak{P}-\left\{ ...
3
votes
1answer
109 views

Extending the zeta function to semiprimes, etc.

The Riemann Zeta function is defined for $s > 1$ as \begin{align} &\prod _{n=1}^{\infty}\dfrac{1}{1 -\ p_{n}^{\ \ -s}}\\ \end{align} It is possible to extend the zeta function to semiprimes ...
0
votes
1answer
44 views

Proving $m$ is prime when $a^{m-1}\equiv 1\pmod m$ and factors of $m-1$ satisy $a^n\equiv r\pmod m,r\neq1$

If $a^{m-1}\equiv 1\pmod m$, and all factors of $m-1$, say $n (n< m-1)$ satisfy $$a^n\equiv r\pmod m,r\neq1$$ then $m$ is a prime. I want to prove this proposition, but it is a little difficult ...
5
votes
1answer
53 views

Choosing primes uniformly at random

I'm interested in efficient methods of generating prime numbers in a given range [a, b] (or with a given number of bits/digits, etc.). By "efficient" I mean minimizing time, randomness, and perhaps ...
7
votes
1answer
182 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 = ...
7
votes
1answer
173 views

A little more on $\sqrt[3]{\cos\bigl(\tfrac{2\pi}7\bigr)}+\sqrt[3]{\cos\bigl(\tfrac{4\pi}7\bigr)}+\sqrt[3]{\cos\bigl(\tfrac{8\pi}7\bigr)}$

Using a special case of an identity by Ramanujan, we find that given the roots $x_i$ of $$x^3 + x^2 - (3 n^2 + n)x + n^3=0\tag1$$ which, since its discriminant is negative, always has three real ...
0
votes
2answers
91 views

Prove that as $x\to\infty $, $\sum\limits_{p \leq x} \frac{1}{p \log \log p} \approx \log \log \log x$

Prove that as $x\to\infty$, $$\sum_{p \leq x} \frac{1}{p \log \log p} \approx \log \log \log x$$ Here sum is taken over primes.I tried to use the partial summation formula but could not ...
1
vote
2answers
25 views

Let $p \in \lbrace2,3,4,…\rbrace$. Suppose that for all $x,y \in \mathbb{Z}$, if $p \mid xy$, then $p \mid x \vee p \mid y$. Show that $p$ is prime.

I'm studying for an upcoming exam and came across this question in my textbook. I'm assuming the easiest way to approach this proof is by contradiction. I don't have much so far, I just suppose that ...