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

3
votes
2answers
597 views

Questions regarding p-adic expansion and numbers

As opposed to real number expansions which extend to the right as sums of ever smaller, increasingly negative powers of the base $p$, $p$-adic numbers may expand to the left forever, a property ...
2
votes
0answers
51 views

Greatest prime factor of $\left(\dfrac{n(n+1)}{2}\right)^2-1$.

Consider $$ \left(\dfrac{n(n+1)}{2}\right)^2-1. $$ Is is possible to say something about the lower bound on the greatest prime divisor of the above expression depending only on $n$? I surfed through ...
1
vote
0answers
42 views
12
votes
2answers
545 views

Diophantine equation involving prime numbers : $p^3 - q^5 = (p+q)^2$

Find all pairs of prime nummbers $p,q$ such that $p^3 - q^5 = (p+q)^2$. It's obvious that $p>q$ and $q=2$ doesn't work, then both $p,q$ are odd. Assuming $p = q + 2k$ we conclude, by the equation, ...
4
votes
5answers
67 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
0
votes
0answers
52 views

Can this relationship be expressed algebraically?

$\frac{\left(x-1\right)!+1}{x}=\frac{\left(y-1\right)!+1}{y}$ When I graphed it, I noticed that it bears a resemblance with the equation (which could of course be completely coincidental): ...
0
votes
1answer
42 views

Show $ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}$

I conjecture that $$ \left\lfloor\frac{2n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \in \{ 0, 1 \}. $$ I know that it is always nonnegative, and equals $1$ for $n < p \le 2n$, ...
19
votes
1answer
1k views

Is this proof of the infinitude of primes valid?

The current issue (May 2015) of the American Mathematical Monthly has a one-line proof that there are an infinite number of primes, and I don't see why it is correct. Here is the proof: If the set ...
3
votes
2answers
49 views

Let $S(x)=\sum_{p\le x,\; q\le x,\; pq\gt x}\frac{1}{pq}$, where p and q are primes. Find the limit of this function.

Let $$S(x)=\sum_{p\le x,\; q\le x,\; pq\gt x}\frac{1}{pq},$$ where $p$ and $q$ denote prime numbers. Show that as $x\to\infty$,$S(x)$ converges to a constant, and find the value of that constant. ...
3
votes
2answers
30 views

Show $ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \log n + O(1)$

Any hints how to prove for $n \in \mathbb N$ $$ \frac{1}{n} \sum_{p \in \mathbb P} \left\lfloor \frac{n}{p} \right\rfloor \log p = \log n + O(1) $$ where $\mathbb P$ denotes the set of all primes? As ...
3
votes
1answer
44 views

Can $\sigma(n)-n$ be a proper divisor of $n$?

Let $n\ge 2$ be a natural number, $\sigma(n)$ the sum of its divisors. Can $\sigma(n)-n$ be a PROPER divisor of $n$ ? If $\sigma(n)-n=n$ , $n$ is a perfect number. If $\sigma(n)-n=1$ , $n$ is a ...
0
votes
0answers
38 views

All primes in the form 4x + 1 can be written as a sum of two squares. [duplicate]

Because all primes other than 2 are odd, one of the two perfect squares must be odd, with the other being even. Is there any way to prove the statement, or is it just an observation?
0
votes
0answers
28 views

Probabilistic primality test for Mersenne numbers

Maybe you know of any probabilistic algorithms specifically checking primality Mersenne numbers? I am not talking here about a universal algorithm (example: the Miller-Rabin test). I'm talking about ...
2
votes
2answers
147 views

Special representation of a number

How can I check, if a number $n$ can be representated by $$pq+rs$$ where $p,q,r,s$ are pairwise different prime numbers with the same number of digits. For example, $$105153899965560312960 = ...
4
votes
1answer
69 views

Non existence of absolute euler pseudoprimes

A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the ...
0
votes
1answer
49 views

Is this a valid equivalent expression of the twin prime conjecture?

The twin prime conjecture states that it is possible to find two primes $p$, $p+2$ at a distance $2$ that are as big as wanted (Wikipedia). I am learning about the basic properties associated to the ...
2
votes
1answer
106 views

Estimating total number of twin primes

Taking my notation from a previous question Define a function $P_6$ as $$P_6(n)=\begin{cases} 0, \ \ 6n-1 \not\in \mathbb P \wedge 6n+1 \not\in \mathbb P \\ 1, \ \ (6n-1 \not\in \mathbb P \wedge ...
1
vote
0answers
79 views

$p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?

Let $p$ be a prime number , then is it true that $p^2| {pa \choose pb}-{a \choose b} , \forall a,b \in \mathbb N$ ?
5
votes
1answer
74 views

Can $2^{M^N}+M^{N^2}$, where $M$ and $N$ are odd primes, never be a prime?

Q: Is number of the form $$\displaystyle 2^{M^N}+M^{N^2}$$ always composite for $M,N$ odd primes? I observed that: If $M=N$ then this number is absolutely a composite, because it satisfies the ...
1
vote
1answer
23 views

Clarification of a proof of Eisenstein's lemma

I'm working on a proof of quadratic reciprocity following Wikipedia's proof via Eisenstein, and one line in the proof seems unjustified: On the other hand, by the definition of $r(u)$ and the ...
6
votes
0answers
67 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
2
votes
0answers
21 views

Generalization of a Result Concerning Projective Planes

Let $\mathcal P$ denote the set of all possible orders of projective planes. For $q\in\mathcal P$, let $PG_2(q)$ denote the projective plane of order $q$. There is a theorem due to James Singler ...
3
votes
2answers
421 views

Is it a composite number? [duplicate]

How do I prove $19\cdot8^n+17$ is a composite number? Or is that number just a prime? So I tried to find a divisor in the cases $ n = 2k $ and $ n = 2k + 1 $. But I had no success. Do you have any ...
2
votes
3answers
88 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
0
votes
1answer
68 views

Foolproof primality test

I just happened to hear about a prime number test which works 100% of the cases in an university lesson about cryptography. It should be something like: if $p$ divides every coefficient of ...
1
vote
0answers
42 views

Is it true that $(1+\varepsilon)\pi(x+y)\ge\pi(x)+\pi(y)$?

Recently I was going through Udrescu's result concerning the inequality $\pi(x)+\pi(y)\ge\pi(x+y)$ which states that ($\pi(x)$ denotes the prime counting function), For all $\varepsilon>0$ and ...
1
vote
2answers
38 views

When $\pi(x) \leqslant 0.4x +1$?

It is claimed here (Lemma 2.2) that $\pi(x) \leqslant 0.4x +1$ when $x\geqslant 7.5$. Is it really so? I am very confused about the proof. Here $\pi(x)$ is the number of primes that do not exceed ...
2
votes
0answers
70 views

Does the Euler product for the Dirichlet $\beta$-function converge for all $\Re(s)>\frac12$?

The Dirichlet $\beta$-function is defined for $\Re(s)>0$ as: $$\beta(s) = \sum_{n=0}^\infty\frac{(-1)^n}{(2n+1)^s}$$ It has the following Euler product (I used that Dirichlet character ...
0
votes
1answer
93 views

Applications of $p_{n+2}+p_{n+1} \le p_1p_2…p_n , \forall n >2$?

Let $p_n$ denote the $n$-th prime number ; I know that $p_{n+2}+p_{n+1} \le p_1p_2...p_n , \forall n >2$ . I am looking for some applications of it , for example I know one application of it ...
6
votes
1answer
35 views

Where $ax + b$ prime infinitely often, is $ax + b - 2$ semiprime at least once?

I'm trying to figure out a way to prove this: Given arithmetic progression $ax + b$ where $a$, $b$ coprime and $ax + b$ is prime infinitely often, it is the case at least once that $ax + b - 2$ is ...
3
votes
1answer
55 views

Why are the distances of $n$ to the closest non-adjacent coprimes always a prime number?

I have observed that the distance of any $n\in\Bbb N$ to its closest non-adjacent (smaller or greater than $n$ at a distance $\not=$ 1) coprimes is always a prime number. Def: $\forall n\ ...
-1
votes
1answer
380 views

Mean of highest exponent in prime factorization of all integers ≥ 2

For any natural number $n > 1$, define $E(n)$,to be the highest exponent to which a prime divides it. For instance, $E(12)=E(36)=2$. Show that $$\lim_{N \to \infty} \frac{1}{N} \sum\limits_{n=2}^{N} ...
-4
votes
0answers
61 views

Is $2^{205379}+59^9$ a prime number?

Is $2^{205379}+59^9$ a prime number (it has almost 62000 digits) ? I have difficulty for calculate it,but I am 99% sure it is not a prime,I found this number is not divisible by small primes up to ...
1
vote
1answer
79 views

Prime number of the form $A^{B^C}+D^{E^F}$

My Brother asked me what is the smallest prime number of the form $A^{B^C}+D^{E^F}$ where A,B,C are three distinct prime numbers, and D,E,F are 3 distinct primes that is Permutations of those 3 ...
2
votes
1answer
41 views

Is there anything I could read that talks about dimensionality of prime/composite numbers?

Is there anything out there that talks about how primes are one dimensional numbers and composites can only be in dimensions greater than 1? What I mean is, 4 would be a two dimensional number (2x2) ...
0
votes
1answer
44 views

Prime numbers of the form $P^Q+R^S$

Is there a prime number of the form $P^Q+R^S$ where $P,Q,R,S$ are four distinct prime numbers? Examples: $2^3+7^5$, $2^3+5^{11}$ are not primes, $2^5+11^7$ is not a prime.
2
votes
1answer
65 views

Why do the closest primes whose distance $d \gt 1$ to $c(n)=\frac{(n+1)!+n!}{2}$ have always $d \in \Bbb P$?

I have made the following observation: define the center of $n!$ and $(n+1)!$, $c(n)$, as the number located exactly in the middle of $(n+1)!$ and $n!$. Def: $\forall n \gt 2\ , \ ...
9
votes
1answer
68 views

Is there any polynomial function $f$ such that If $\gcd(p,q)=1$ then $\gcd(f(p),f(q))=1$ for all such $p,q$?

Is there a polynomial, $f(x)$, such that for all natural numbers $p$ and $q$, if $\gcd(p, q) = 1$ then $\gcd(f(p), f(q)) = 1$? Note : Function $f(x)$ must be a polynomial in $x$, not depend on $p$ or ...
5
votes
4answers
263 views

How do we identify twin primes .

as known , each prime number greater than 3 is of the form $6k-1$ or $6k+1$ . twin primes are all sort of two adjacent primes of difference $= 2$ as: $$(11,13) ,(17,19),\ldots,(6k-1,6k+1)$$ -Is ...
3
votes
0answers
39 views

Do the second-last-digits of the primes $\ge 11$ form a transcendental number?

Suppose, the number $x$ is constructed from the second-last-digits from the primes $\ge 11$ The first $1996$ digits of $x\ =\ 0.11112...$ after the decimal point are : ...
6
votes
8answers
341 views

If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
2
votes
1answer
47 views

Is equivalent this expression to Wilson's theorem?

According to Wilson's theorem, $n$ is prime if and only if (1): $$(n-1)! \equiv -1 \pmod{n}$$ Would the following expression be valid and equivalent? (2) ...
4
votes
0answers
104 views

Test about prime gaps

I did the following test: For every prime, take the prime gap distance $dp$ to the previous prime and the next prime $dn$, then calculate $a=(pp\ mod\ dp)$ and $b=(np\ mod\ dn)$. If $a$ or $b$ ...
4
votes
1answer
61 views

Why are there not primality tests based on comparing the candidate $n$ with values of some $k \in [0,n]?$

I am learning basic number theory and as far as I could read, basically all the primality tests (or proven primality theorems) that are able to decide if a given $n$ is prime (or a special ...
0
votes
1answer
37 views

What is the asymptotic behavior of the function counting the number of (not necessarily distinct) prime divisors?

From http://en.wikipedia.org/wiki/Arithmetic_function#.CE.A9.28n.29.2C_.CF.89.28n.29.2C_.CE.BDp.28n.29_.E2.80.93_prime_power_decomposition Ω(n), ω(n), νp(n) – prime power decomposition The ...
0
votes
2answers
495 views

How to determine if a number $A$ is divisible by all the prime factors of $B$?

How to determine if a number $A$ is divisible by all the prime factors of $B$? For example: $120,75$ $A=120=2^3\times3\times5$ and $B=75=3\times5^2$ Therefore yes, $A$ is divisible by the prime ...
3
votes
2answers
65 views

Does $p^n$ divide $\binom{p^{n+m-1}}{m}$?

Let $n, m \in \mathbf N$ and $p$ an odd prime number. Then does $p^n$ divide $\binom{p^{n+m-1}}{m}$ ? It seems true, but I can not find a clue. Can I have any hint?
1
vote
2answers
50 views

Show that $10^{n(p-1)}\equiv 1\pmod{\! 9p}$ for $p\ge 7$

I need to prove that for each prime $p \ge 7$ and for each $n \in\Bbb N$ $$10^{n(p-1)} \equiv 1 \pmod {9p}$$ What I've tried: I know $10$ is coprime to $9$ and $p$, so it is coprime to $9p$. I ...
4
votes
1answer
47 views

Prime numbers distribution theorem

I'm trying to understand Gauss' theorem: $$ \frac{\pi(x) }{x/\ln x} \to 1 $$ for large $x$. I've taken the list of first 1000 prime numbers from Utah university site, saved them to file ...
1
vote
1answer
30 views

How many numbers have more primes than half that number?

If I have a number $n$ and I count all the prime numbers below $n$, for how many numbers will there be more primes below $n$ than half of $n$?