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

8
votes
2answers
182 views

$\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ implies $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2}$; where $p>3$ is a prime?

From $\binom{2p-1}{p-1}\equiv 1\pmod{\! p^2}$ how does one get $\binom{ap}{bp}\equiv\binom{a}{b}\pmod{\! p^2},\,\forall a,b \in \mathbb N,\, a>b$; where $p>3$ is a prime ?
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$, ...
4
votes
5answers
68 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 ...
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 ...
4
votes
1answer
24 views

Prove that for any prime $p$, if $a>b$ then $p^2$ divides $C(pa,pb)-C(a,b)$.

Let, $p$ be a prime and $a>b$. If $\operatorname{C}(n,r)$ denotes the combination of $r$ objects from a collection of $n$ objects taken at a time, prove that ...
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$ ?
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
69 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 ...
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 ...
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
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
422 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 ...
1
vote
0answers
43 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 ...
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 ...
2
votes
0answers
73 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 ...
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\ ...
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 ...
-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 ...
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.
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 ...
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 ...
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 ...
2
votes
1answer
66 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\ , \ ...
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 : ...
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) ...
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 ...
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$?
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 ...
0
votes
1answer
26 views

Gaps between primes and prime counting function

With two consecutive primes $p_n$ and $ p_{n+1}$ how many solutions does the inequality $$\frac {p_{n+1}-p_n}{2}\ge\pi(p_n) $$ have with $\pi(n) $ being the prime counting function
-1
votes
1answer
36 views

Is there a proof that every prime containing only the digit “1” must have a prime as its digit sum? [closed]

Verbal proof is preferred as I'm not to familiar with mathematical notation.
-4
votes
2answers
67 views

Is this number prime or composite?Prove your answer [closed]

Is the number $1111...$($91$ times $1$) prime or composite? I have tried to break it into multiples of 10,but that just gave me a huge binomial expandum.
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. ...
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 ...
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 ...
4
votes
1answer
70 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
29 views

Question about inequalities between consecutive primes

Can any two consecutive primes $p_n$ and $p_{n+1}$ satisfy the inequality $3p_n+1<2p_{n+1}$
4
votes
1answer
45 views

Prime - composite numbers

Let $n>2$ a natural number. We define the following sets: $$S=\{1 \leq a \leq n : (a,n)=1, a^{n-1} \not\equiv 1\pmod n\} \\ T=\{1 \leq b \leq n : (b,n)=1, b^{n-1} \equiv 1 \pmod n\}$$ Are there ...
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
1answer
310 views

What meaning could possibly $m\simeq_{prim}n$ have?

For positive integers, what does $m\simeq_{prim}n$ means? I have this: Let $\alpha\in\mathbb Z \wedge n\;$ positive integer. If $\alpha\simeq_{prim}n$, then ...
3
votes
3answers
74 views

Proving that $45$ is composite using Fermat's Little Theorem

I am trying to prove that $45$ is composite using Fermat's Little Theorem. I am given a hint which states: "Find an integer $b$ such that $b^{45} \not \equiv b \pmod{45}$ and explain why this implies ...
4
votes
2answers
130 views

Prime number question?

If I want to calculate all the primes, could I do this? Let $N = \{2,3,4,5,6,7,8,..\}$ Then the elements in $N - NN$ are prime? Because they are the ones that aren't composite?
1
vote
0answers
65 views

Which fields of math would I need to study to fully understand/solve the Riemann Hypothesis?

Apart from analytic number theory / complex analysis to actually knowing what it's about, which fields of math should I master to have a chance at solving it? I understand that the answer may come ...
3
votes
1answer
49 views

Finding the number of primes numbers using exclusion/inclusion principle: What am I doing wrong?

I want to find the number of primes numbers between 1 and 30 using the exclusion and inclusion principle. This is what I got: The numbers in sky-blue are the ones I have to subtract. The others are ...