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
0answers
75 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
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\ , \ ...
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
265 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
106 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
38 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
496 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$?
-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.
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
3
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 ...
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
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 ...
28
votes
16answers
33k views

Real world applications of prime numbers?

I am going through the problems from Project Euler and I notice a strong insistence on Primes and efficient algorithms to compute large primes efficiently. The problems are interesting per se, but I ...
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 ...
0
votes
0answers
56 views

Is there a definition about prime pairs $(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$?

I am studying congruences and I have observed this kind of prime pairs $(p,q)$ related to odd numbers. Do this kind of prime pairs have a name or have been studied before? Here is the definition: ...
3
votes
0answers
46 views

Is there an advantage in using continued fractions for Catalan or Fibonacci-Lucas primality tests?

I am studying the basic theory about continued fractions and as usual after reading basic concepts I reviewed here at MSE former questions to learn more. While reviewing the questions and answers, I ...
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
2answers
42 views

Is it true that $(pq,(p-1)(q-1)) =1 \iff (pq,lcm(p-1,q-1))=1$?

Notation: $(a,b) = \gcd(a,b)$ If $p,q$ are distinct odd primes, is it true that $$(pq,(p-1)(q-1)) =1 \iff (pq,lcm(p-1,q-1))=1\;?$$
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 ...
1
vote
0answers
31 views

Number of binomial coefficients , ${ n \choose k}$ k $\in$ [0,n] , that are divisible by a prime p?

For a given k, ${n\choose k}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding base p digit of k (consider the p-ary notation for n ...
2
votes
1answer
61 views

Does there exist one number in progression that is coprime to all others? [closed]

Does there exists at least one number in sequence $n,n+1,n+2 ... n+m $ which is coprime to all the others. $n,m$ are positive integers.
-1
votes
2answers
50 views

Why modulo prime prefered over modulo composite?

In encryption process(aes encryption)and also in Galois field, a prime number is always used to perform the modulo operation. So I wanted to know the reason for using only prime numbers for modulo ...
1
vote
2answers
43 views

Given integers $q,n$, is there always an integer $x$ such $x^q - n$ is prime?

Does anybody know if this is true? I can't find references about it, also I can't prove to be true (or false). I think computing $x$ is a brute force task. Thanks (and sorry if I lost some basic ...
1
vote
0answers
25 views

Testing if a number N is prime by its regular polygon's angles

Is it possible to tell if a number N is prime by looking at the angles of a regular N-sided polygon? For example, a regular triangle has 60 degree angles, is there a way to tell that the number 3 is ...
0
votes
1answer
33 views

Probable Candidates for the numbers whose sum of divisors is prime?

What are probable candidates for the numbers whose $\sigma(n)$ (sum of divisors) is prime? I know that the list of probable candidates include perfect squares and odd powers of 2 (specifically only ...
0
votes
1answer
23 views

prove that for every integer $a>0$ there is a unique representation $a=r*s^2$ [duplicate]

I need to prove that for every integer $a>0$ there is a unique representation $a=r*s^2$ where $r$ is not dividable by any square: there is no $d>1$ such that $d^2|r$ What I tried is to show a ...
1
vote
2answers
54 views

show that $\lim(\pi(x)/x) = 0$

I need to show that: $$\lim_{x\to\infty}(\pi(x)/x) = 0$$ Where $\pi(x)$ is the number of primes smaller then $x$. I tried using the fact that: $$\pi(x)<(1-1/2)(1-1/3)...(1-1/k)X + O(1)$$ but ...
3
votes
2answers
46 views

Proving infintely many primes of the form 6k-1

I have seen the past threads but I think I have another proof, though am not entirely convinced. Suppose there are only finitely many primes $p_1, ..., p_n$ of the form $6k-1$ and then consider the ...
7
votes
3answers
575 views

Proof of Wolstenholme's theorem

According to the theorem, if $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots+\frac{1}{p-1} =\frac{r}{q}$$ then we have to prove that $r\equiv0 \pmod{p^2}$. (Given $p>3$, otherwise ...
0
votes
0answers
51 views

What is this pattern in this calculation using primes?

So i was bored and when i get bored i write small programs that calculate something. This time i did this: I searched for the amount of primes bellow 10,000,000 using Sieve of Eratosthenes starting ...
1
vote
1answer
42 views

How n (1+b) is not prime?

Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ...