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

2
votes
1answer
63 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
0answers
18 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
19 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
116 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
55 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?
0
votes
0answers
129 views
+300

If this inequality holds for $n$ larger than some $N$, what is an upper bound to $N$?

Let $p_n$ be the $n$-th prime and set $k_1=10;k_2=6;k_3,k_4=4;k_5,k_6=3;k_7,\ldots ,k_{n+1}=2$. For large enough $n$, prove or disprove that ...
5
votes
0answers
41 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 ...
0
votes
1answer
37 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
27 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
158 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
39 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
59 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 ...
1
vote
0answers
99 views

Is there a formula telling if number is prime? [closed]

Like the topic.. . I mean.. let's say i'm wondering if 15 is prime or not. Could i calculate it, like function roots? EDITED: I mean something like columbus8myhw said: How about: Define ...
1
vote
0answers
26 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
61 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
101 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
58 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 ...
1
vote
2answers
69 views

About the infinitude of some kind of primes? [closed]

I will propose this proof: I am not sure about the arguments used in this proof. So I put this proof here for more discussions.
2
votes
3answers
53 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
99 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
43 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
43 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
0answers
111 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-2mx+N = ...
7
votes
0answers
117 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
69 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
22 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 ...
4
votes
1answer
38 views

equivalence between Chebyshev estimation and pi estimation in PNT

I searched, but though many posts are close, none of them are dublicates. Our version of PNT states that there is some $c$ s.t. $$\psi(x)=x+O(x\exp(-c\sqrt{\ln x}))$$ We have to prove equivalence ...
21
votes
2answers
898 views

Unusual pattern in the distribution of odd primes

I have recently noticed an unusual pattern in the distribution of odd primes. Each one of the following sets contains approximately half of all odd primes: $A_n=\{4k+1: 0\leq k\leq ...
0
votes
0answers
12 views

Is it ever possible for hypercomplexes to generate every element modulo a prime?

To start, we can take a well-chosen complex number, modulo a prime $p$, and generate every complex element modulo $p$. For example, if we take $(1+2i)^k \pmod 3$, each power of $k$ up to $(3 \cdot 3 ...
13
votes
2answers
654 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 ...
1
vote
0answers
23 views

How quickly can we multiply hypercomplexes?

If we start with a hypercomplex number with $2^n$ entries, how quickly can we multiply it by another hypercomplex number, modulo a prime? EXAMPLE For example, with $n=1$, we get the complex numbers. ...
0
votes
2answers
40 views

let $G$ to be finite abelian group of order O(G), let n to be prime number and (O(G),n)=1 prove that $g=x^n$ for any $ x \in G$

let $G$ to be finite abelian group of order O(G), let n to be prime number and (O(G),n)=1 prove that $\forall g \in G$ we can write $g=x^n$ for any $ x \in G$
3
votes
2answers
64 views

Do we still need probabilistic primality testing methods for practical applications?

Probabilistic primality testing methods like Rabin Miller and Solovay Strassen, were created at the time when mathematicians were not sure whether there is a deterministic polynomial algorithm. After ...
0
votes
3answers
45 views

Help explain the end of this proof for infinitely many primes?

by contradiction, assume finitely many primes $p_1, p_2,\cdots, p_k$. let $N = p_1p_2\cdots p_k + 1$. Note $N > 1$. Now, by the fundamental theorem of arithmetic, there exists a number $p_j$, where ...
0
votes
0answers
26 views

Minimization problem involving a set of prime numbers and modular arithmetics

I'm a student working for curiosity on a general minimization problem where I suppose that there is no efficient algorithm for solving it. I'd like to ask for your valuable advice. Let $P$ be a set ...
3
votes
0answers
79 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
1
vote
0answers
34 views

Numbers with special factorisation

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all ...
6
votes
1answer
123 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
1
vote
1answer
77 views

Generalizing Bertrand's Postulate

Is it possible that for any integer $y \ge 2$, there exists an integer $x$ such that if an integer $n \ge x$, then for all integers $z \le n^y$, there exists a prime $p$ such that $z \le p < z+n$ ...
1
vote
1answer
29 views

Fermat's Little Theorem - Prim. Root - Find x

So I am studying for finals and I am not able to solve the problem: Let $p=3∗2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x \equiv 3 \mod p$ Any guidance ...
3
votes
1answer
30 views

Find an integer $x$ such that $2^x \equiv 3\pmod{p}$ given prime $p$

So I am studying for finals and I am not able to solve the problem: Let $p=3\times2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $$2^x \equiv 3 \pmod p$$ Any ...
1
vote
2answers
62 views

Properties of prime mod $3$

We know that if $p$ is a prime congruent to $3 \mod 4$, we cannot represent it as sum of two squares. Is there a positive property of such $p$? That is, do we have any statements that say "$p$ is a ...
-2
votes
3answers
104 views

Which number is odd one out in set $\{5, 7, 11, 29, 41\}$ [closed]

Which of the set element should not belong to set? $$\{5, 7, 11, 29, 41\}$$
1
vote
2answers
26 views

How to find smallest integer which is greater than N positive primes

I know this can't be computed exactly, but I just need a rough estimate. I know one can compute a rough estimate of the number of primes less than N using the famous formula: ...
1
vote
1answer
41 views

Solving $x^n \equiv a \text{ (mod } p)$ in $\mathbb{Z}$

I want to show that for any integers $a$ and $n,$ ($n > 1$) there are infinitely many primes $p$ such that $$x^n \equiv a \text{ (mod } p).$$ When $n$ is odd, I used the fact that if $(a,p)=1$ ...
3
votes
3answers
33 views

Proving that a number has at least 3 distinct prime factors.

Let abc be a 3-digit natural number (written in base 10). Prove that the 6-digit number abcabc has at least three distinct prime factors. I know that to prove that the 6-digit number has at ...
0
votes
1answer
27 views

Constellations in $\Bbb P^n$

In one of his papers Tao shows that set of Gaussian primes $\Bbb P[i]$ contains arbitrarily shaped constellations (where "shape" is any set of Gaussian integers and "constellation" of that shape is ...
4
votes
7answers
86 views

Primality of number 1

Is number 1 prime as per the definition of prime numbers? Because as per the definition for being prime it should be divided only by 1 and number itself.
0
votes
2answers
67 views

Make a prime number from specified number, by concatenating some more digits on its right?

I am given a number, I don't know whether it's prime or not. The algo says, For eg - Step 1 - Convert char to ints. (Hello - 72101108108111) Ascii values Step 2 - Make a large number. Convert char ...