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
1answer
77 views

If $f(x)$ is prime, then $f(x^{f(x)})\bmod f(x) = 0$?

I'm aware this is an extremely amateur question but I really don't know where else to ask it. Can anybody find a counterexample for the following conjecture? Given $f$ such that ...
0
votes
1answer
81 views

Compare two sums using prime number theorem

Let $$A(x)=x\sum_{p \leq x} 1, B(x)=\frac{3}{5}\sum_{x<p\leq 2x}p$$ Using prime number theorem, we have $A(x)\sim\frac{x^2}{\log{x}}$, but how to obtain an estimation for $B(x)$?
1
vote
1answer
59 views

Sequences of the form : $p_n=2^{p_{n-1}}-a$?

There is known Catalan sequence : $C_n=2^{C_{n-1}}-1$ , with $C_0=2$ I have noticed that following sequence produces prime numbers for the first four terms (I don't know if the fifth term is a prime ...
6
votes
1answer
145 views

Special types of extensions of fields

Let $K$ be a field. Let $p$ be any prime number. Can one always construct an algebraic extension $K_p$ of $K$ with the following properties? (1) If $L$ is a finite extension of $K$ contained in ...
3
votes
1answer
1k views

Are there infinitely many Mersenne primes?

known facts : $1.$ There are infinitely many Mersenne numbers : $M_p=2^p-1$ $2.$ Every Mersenne number greater than $7$ is of the form : $6k\cdot p +1$ , where $k$ is an odd number $3.$ ...
0
votes
2answers
145 views

Prove a property of divisor function

Let $n$ be a positive natural number whose prime factorization is $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where $p_i$ are natural distinct prime numbers, and $a_i$ are positive natural numbers. ...
6
votes
2answers
276 views

How do I investigate the metamathematics of Euclid's proof of infinitude of primes?

Is primeness a predicative property? Earlier this year, I jotted down some thoughts in a paper whether Euclid's proof of infinitude of prime numbers is tautological arguing that prime numbers are ...
2
votes
3answers
1k views

Show that every $n$ can be written uniquely in the form $n = ab$, with $a$ square-free and $b$ a perfect square

I need to show that every positive integer $n$ can be written uniquely in the form $n = ab$, where $a$ is square-free and $b$ is a square. Then I need to show that $b$ is then the largest square ...
1
vote
2answers
759 views

Prime factorization rules

When you have a number like 81. Is it safe to assume that if the number can't be divided by 2 or 3 that it's prime if it ends with a 1?
6
votes
3answers
171 views

Showing $\pi(ax)/\pi(bx) \sim a/b$ as $x \to \infty$

I'm having a bit of a problem with exercise 4.12 in Apostol's "Introduction to Analytic Number Theory". I don't think it's supposed to be a very hard exercise, it's the first one in its section ...
1
vote
1answer
487 views

Infinitely many primes of the form $6\cdot k+1$ , where $k$ is an odd number?

How to prove that there are infinitely many primes of the form $6k+1$ , where $k$ is an odd number ? Here is a proof that there are infinitely many primes of the form $6k+1$ : We will assume that ...
5
votes
2answers
396 views

No prime number between number and square of number

Find the values of $x \in \mathbb{Z}$ such that there is no prime number between $x$ and $x^2$. Is there any such number?
17
votes
1answer
602 views

Primes of the form $x^2 +ny^2$ where swapping $x$ and $y$ still gives a prime

I am studying primes of the form $x^2+ny^2$, and i was wondering if there are any known results about the primes of this form such that when you swap $x$ and $y$ you also get a prime. ie for ...
3
votes
0answers
188 views

Number of integral solutions

Given a prime number $p$, find the number of pairs of integers $(a, b)$ such that $p \lt a$, $p \lt b$ and $ab$ is divisible by $(a-p)(b-p)$.
10
votes
2answers
315 views

Take any number and keep appending 1's to the right of it. Are there an infinite number of primes in this sequence?

Ignoring sequences that are always factorable such as starting with 11, Can we take any other number such as 42 and continually append 1s (forming the sequence {42, 421, 4211, ...}) to get a sequence ...
5
votes
3answers
252 views

Evaluate $d(n!)$

An exercise: Using the prime number theorem find an asymptotic expression for $d(n!)$ where $d$ is the number of divisors.
4
votes
1answer
237 views

$16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
12
votes
2answers
386 views

How rare are the primes $p$ such that $p$ divides the sum of all primes less than $p$?

This is just for fun! The title pretty much says it all. It's probably a very difficult question. Up to the $40,000^{th}$ prime $(479909)$, I have found only $5$, $71$ and $369119$ with this ...
1
vote
0answers
159 views

Forcing and divisibility

I'm going to bring together a couple of seemingly unrelated questions that I've asked here. This may be silly. Or maybe not? Imagine that $n$ is some sort of infinitely large integer, and thus so ...
0
votes
1answer
130 views

Is there a closed form to $a^b \bmod b$ if $b$ is not a prime?

We know $$a^p \equiv a \pmod p\quad p\text{ a prime, }0\leq a \leq p-1.$$ But if we have $b$, not prime, what's the new formula? $$a^b \equiv\ ? \pmod b,\quad b\text{ not a prime, } 0\leq a \leq ...
2
votes
0answers
33 views

What is a good tool for this job involving the prime spiral?

I'm interested in studying the prime spiral interactively. This question talks about some interesting patterns in the spiral involving quadratic equations. The idea I had was, write a program that ...
0
votes
2answers
224 views

computing primes

As per my knowledge, I have seen the only following functions which will produce primes for $n$: $n^2 - n + 41$ $n^2 + n + 41$ Of course both functions faile for $n = 41$ due to the polynomial ...
1
vote
1answer
267 views

Calculation of prime numbers - why so difficult?

As I read more and more about advanced mathematics, the more complex and obscure topics seem to be tougher to bend the rules of math to describe. However, the simple (and undoubtedly very useful) ...
40
votes
1answer
1k views

Sums of prime powers

You are given positive integers N, m, and k. Is there a way to check if $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ faster than computing the (modular) sum? For concreteness, you ...
2
votes
1answer
185 views

Could this $100000004$ digits number be candidate for the record prime number?

Let's observe following number : $ 4517\cdot 2^{332192811}+1$ I have noticed : If $k\cdot 2^{2n+1}+1$ is prime number then $\gcd(k-1,3)=1$ , where $k,n \in Z^{+}$ , so $\gcd(k-1,3)=1$ should ...
0
votes
1answer
63 views

If $P_1P_2…P_{n_0} + 1$ is prime and $2$ divides $P_2P_3…P_{n_0}+1$ is $(P_2P_3…P_{n_0} +1)/2$ prime or composite or both?

If $P_1P_2\cdots P_{n_0} + 1$ is prime, and 2 divides $P_2P_3\cdots P_{n_0}+1$, is $(P_2P_3\cdots P_{n_0} +1)/2$ prime or composite or both? Here $P_i = \{{ 2,3,5,7 \dots\}}$ Composite numbers are ...
1
vote
1answer
266 views

Are there infinitely many primes of the form $p_1\cdot p_2\cdot…p_n+1$? [duplicate]

Possible Duplicate: Is there an infinite number of primes constructed as in Euclid's proof? The question is : Are there infinitely many primes of the form $p_1\cdot ...
3
votes
3answers
384 views

Calculating $\pi(x)$ , a new idea?

I am asking myself if instead of working with the primes in the calculation of $\pi(x)$ up to $x$, we instead work with the composite numbers and then using a simple subtraction to get $\pi(x)$. After ...
0
votes
1answer
159 views

Is the set of logarithms of $N$-almost primes equidistributed?

Given the set of all primes. From this one builds subsets of $N$-almost primes according to a certain partition, e.g. $\lambda=(3,1)$, so the set is $$ M=\{2^33,2^35,2^37,...,3^32,3^35,...\}. $$ Is ...
5
votes
1answer
153 views

A trivial but maybe nonetheless non-trivial method of inferring primality

The topologist J. H. C. Whitehead (not to be confused with his famous uncle) said it is naive to think a theorem is trivial merely because its proof is trivial. Hence I'm wondering if a certain ...
2
votes
2answers
216 views

Shapes and sizes of finite sets of prime numbers

Knowing that $p$ is prime enables us to rule out the possibility that $p+2$ and $p+4$ are both prime, except in the one trivial case that $p=3$, since at least one of $p,\ p+2,\ p+4$ is divisible by ...
0
votes
1answer
140 views

Integer polynomials with $p$ dividing $f(p)$

If $f \in \mathbb{Z}[x]$ is such that $p \mid f(p)$ for all primes $p$, then $x \mid f(x)$ in $\mathbb{Z}[x]$. This follows by writing $f(x) = \sum \limits_{i=0}^d c_i x^i$ and noting that $c_0 \equiv ...
1
vote
1answer
107 views

Relations between coefficient and exponent of Proth prime form $k\cdot 2^n+1$?

Definition: Proth number is a number of the form : $$k\cdot 2^n+1$$ where $k$ is an odd positive integer and $n$ is a positive integer such that : $2^n>k$ My question : If Proth number is prime ...
1
vote
1answer
208 views

Prime numbers which solve $2^s=1\pmod p$

Here we define those primes $p$ for which $\operatorname{ord}_p(2)=s$, where $s$ is the minimum of the set $S$ of all divisors $d\mid p-1$ such that $2^d-1\geq p$. For example: for $p=7$, $s=3$, ...
0
votes
1answer
48 views

How to prove this modular criterion for prime numbers of the form $p=2^n \pm a$?

How to prove following statement : For prime numbers $p$ greater than $3$, it is true that: if $p=2^n-a$ and $a\equiv 1 \pmod 6$ then $p\equiv 1\pmod 3$ if $p=2^n+a$ and $a\equiv 5 \pmod ...
14
votes
2answers
799 views

Proof involving induction and primes

I'm looking to prove that: $$p_n \leq 2^{2^{n-1}}$$ Where $p_n$ denotes the $n$th prime in ascending order. The proof method is induction. I've solved my base case, that is: $n=1$ $p_1 = 2$, ...
6
votes
3answers
403 views

Proof that for all distinct primes $p, q$, there exists $n$ so that $p+n$ is prime, but $q+n$ isn't

Imagine two distinct prime numbers $p$ and $q$. Intuitively, I'd say that there is always a natural number n so that $p+n$ is a prime number, but $q+n$ isn't. I was given two hints: for each ...
3
votes
1answer
108 views

Is this proof about the form $2^n \pm a$ correct?

I want to prove following statement : For prime numbers $p$ greater than $3$, it is true that: $a)$ if $p=2^n-a$ and $a=6k+1$, then $n$ is an odd number. $b)$ if $p=2^n+a$ and $a=6k-1$, ...
9
votes
4answers
780 views

How to determine in polynomial time if a number is a product of two consecutive primes?

How to determine in polynomial time if a number is a product of two consecutive primes? All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find ...
12
votes
2answers
235 views

An upper bound for $\log \operatorname{rad}(n!)$

Let $n>1$ be an integer and let $\operatorname{rad}(n!)$ denote the radical of $n$-factorial. (The radical of an integer $m$ being, loosely speaking, the product of the prime divisors of $m$.) Can ...
2
votes
1answer
453 views

Prime power divisors of the fibonacci numbers

I came across a result that if $p^n \mid f_m$ for some $n\geq1$ then $p^{n+1} \mid f_{pm}$. I was wondering if this is true.
3
votes
2answers
250 views

Proofs from the BOOK: Bertrand's postulate Part 3: $\frac{2}{3}n<p \leq n \rightarrow$ no p divides $\binom{2n}{n}$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 9: I have to show, that for $\frac{2}{3}n<p \leq n$ there is no p which divides ...
2
votes
0answers
74 views

Prime numbers of the form: $k\cdot 2^n \pm 1$ , where $k<3n$

Is it true that : For every $n$ there exists a number $k<3n$ such that: $k\cdot 2^n-1$ or $k\cdot 2^n+1$ is prime,where $k,n\in \mathbf{N}$ Maple code that prints least $k$ such that ...
3
votes
0answers
198 views

How to find $\beta$ and $\alpha$?

$\mathbb{P}$ is the prime numbers set. $p \in \mathbb{P}$ $a,b,c \in \mathbb{N}$ $n=a p^b+c$ where $c= n\bmod p$ $b$ is the highest power of $p$ who divides $n-c$ How to find $\beta$ where ...
1
vote
1answer
125 views

Tile $\mathbb{R}^n$ with Primitive Cuboids

For every integer $n$ with $i$ prime factors associate a unique tile in $\mathbb{R}^m$ with $m \ge i$ as such, for every prime factor $p_j$ of $n$, the tile is a cuboid of dimension $m$ with a ...
2
votes
0answers
68 views

Prime numbers of the form : $2^{n+a}+2^{n} \pm 1$ , where $0 \leq a < n$ and $n \equiv 0 \pmod 6$

Is it true that : For any positive integer $n$ such that $n \equiv 0 \pmod 6$ there is at least one prime number of the form: $p=2^{n+a}+2^{n} + 1$ , or , $p=2^{n+a}+2^{n} - 1$ with ...
1
vote
0answers
131 views

Binary sequences in primes

Is anything known about these problems? If we make a string S of 0's and 1's with 1 in n'th position if the the nth prime $p_n$ is of the form $1+m 2^{9^{9^{9^{9}}}}$, else 0, does every finite string ...
2
votes
2answers
119 views

Evaluating two limits related to prime numbers

How to find these limits $\displaystyle\lim_{n\to\infty}\left(\ln(\ln(n)) - \sum_{k=2}^n\frac1{k \ln(k)}\right)$ ? and $\displaystyle\lim_{n\to\infty}\left( \ln(\ln(n)) - ...
3
votes
1answer
181 views

If $2^n+n^2$ is prime number then $n \equiv 0 \pmod 3 $?

Is it true that : $((2^n+n^2) \in \mathbf{P} \land n \geq 3)\Rightarrow n\equiv 0 \pmod 3 $ I have checked this statement for the following consecutive values of $n$ : ...
2
votes
1answer
169 views

Infinitely many primes of the $\sum_{i=0}^{a} n^{i}+m\cdot\sum_{i=0}^{b} n^{i}$ form?

How to show that there is infinitely many prime numbers of the form: $p=\sum_{i=0}^{a} n^{i}+m\cdot\sum_{i=0}^{b} n^{i}$ where: $m\in \mathbb{Z}^{*}$ , $a,b,n\in \mathbb{N}$ , $\gcd(a+1,b+1)=1$ For ...