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
58 views

What's known about primes of the form $m^n+1$?

For example, the Fermat primes are primes of the form $2^{2^n}+1$. I'm wondering if the primes $m^n+1$ have a name. More importantly, I'm wondering if there are tables of these primes, and what else ...
1
vote
2answers
48 views

problem proving this property of congruence and primes

I've been working on this for a few days and I just can't seem to find a good proof for this. Given $a \equiv b\pmod{p_i}$, $i=1,2,3,\dots,n$ and $p_i$ is prime, show that $a \equiv b ...
10
votes
0answers
193 views

Continued fraction with prime reciprocal entries

We know that the reciprocals of the primes form a divergent series. We also know that a necessary and sufficient condition for a continued fraction to converge is that its entries diverge as a series. ...
15
votes
1answer
1k views

Would proof of Legendre's conjecture also prove Riemann's hypothesis?

Legendre's conjecture is that there exists a prime number between $n^2$ and $(n+1)^2$. This has been shown to be very likely using computers, but this is merely a heuristic. I have read that if this ...
0
votes
2answers
146 views

Primes dividing Integers

I randomly choose two integers. What is the probability that a certain prime number p does not divide both integers? Express your answer in terms of p.
1
vote
0answers
174 views

All Sufficiently Large Squares, Represented as Sum of Two Semiprimes

Define a semiprime to be the product of two (not necessarily distinct) primes, $p_iq_i$. Conjecture: All squares $\ge 4^2$ are representable as the sum of two distinct semiprimes. Case 1: Squares ...
2
votes
2answers
82 views

Stategy for prime factorization

How do I prime factorize big numbers, such as 8435674686325652 without having to make millions of divisions?
3
votes
1answer
377 views

Weaker Version of “Goldbach's Other Conjecture”

Taken from problem 46 on Project Euler: It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square. $9 = 7 + 2 \times 1^2$ ...
3
votes
3answers
185 views

Probability for the sum of two random numbers being a prime number?

Suppose $N$ is a (large) fixed positive integer, and one is asked to randomly choose any two integers (numbers could be same as well) from $1$ to $N$ (including $1$ and $N$). Let the experiment be ...
16
votes
2answers
358 views

Question from Putnam '89: Primes of the form $101\ldots01$

I'm not a math major, but would like to compete in the Putnam. As suggested in other questions here, I'm working some old contest problems. I'd like some input on this attempted proof--general input ...
1
vote
1answer
110 views

integral representation of the prime number counting function

the prime counting function obeys the integral equation $$ log \zeta (s) =s \int_{0}^{\infty}dt \frac{\pi (e^{t})}{e^{st}-1} $$ so using the properties of the Mellin transform we have that $$ \pi ...
1
vote
1answer
134 views

On the numerators of Bernoulli numbers

Von Staudt-Clausen theorem implies that $pB_{2n} \in \mathbb{Z}_{p}$ for all primes $p$ and for all $n \in \mathbb{N}$. It means that the highest power of any prime that can occur in the denominator ...
1
vote
1answer
65 views

Common Primes…

In SageMath, the software, I was trying to create a visualization of how common it is for a number to be prime. Can anyone help me with the code? I am a super beginner and lost. I was going to post ...
3
votes
0answers
79 views

How does Hildebrands proof of the prime number theorem via large sieve work?

How does the sieve inequality (I may not know the most general form) lead to the distribution of primes? To me, these concepts do not seem to be related. Can their connection be described in a ...
2
votes
0answers
154 views

Wilson's theorem intuition

Wilson's Theorem: $p$ is prime $\iff$ $(p-1)!\equiv -1\mod p$ I can use Wilson's theorem in questions, and I can follow the proof whereby factors of $(p-1)!$ are paired up with their (mod $p$) ...
10
votes
2answers
315 views

Are closed geodesics the prime numbers of Riemannian manifolds?

I wonder to what extent one can support the analogy that primitive closed geodesics are the prime numbers of Riemannian manifolds? ("Primitive": traced once, as opposed to $m$-fold for $m \ge 2$.) In ...
5
votes
3answers
464 views

Prime Number in triangle

I had a question here, the measures of the sides of a right triangle (a single unit) can be prime numbers? If they can not, why?! But, if you can, could you help me find an example?
8
votes
0answers
254 views

Why are minima of $(k \bmod 4)$-Prime $\zeta$ functions $|P_x(r,t)|$ more frequent for $\frac\pi2\leq t \leq \pi$?

I got these plots when I evaluate the sum of truncated $(k \bmod 4)$-Prime $\zeta$ function, i.e. $$ P_x(r,t)=P_{x;4,1}(-ir\cos t)+P_{x;4,3}(-ir\sin t)=\sum_{x\geq p\;\bmod\;4=3} p^{-ir\cos ...
7
votes
0answers
202 views

The effect of roots of Dirichlet's $\beta$ function condenses to $\frac12\left(1+ie^{i2\pi\frac{p}4}\right)$

With the help of Raymond Manzoni and Greg Martin I was able to derive an explicit formula for the number of primes of the form $4n+3$ in terms of (sums of) sums of Riemann's $R$ functions over roots ...
3
votes
2answers
95 views

Extending primes

This question is more of a curiosity than anything. Start with a prime number and consider concatenating digits onto the right hand side. Sometimes you can make a prime and continue the process ...
0
votes
1answer
55 views

A diophantine equation related to primes.

I have $2$ prime numbers $p_1$ and $p_2$. I have to find the solution of $\large{p_1t_1+p_2t_2=1}$ where $t_1$ and $t_2$ are integers. How do I do this?
2
votes
1answer
290 views

Prove that every highly abundant or highly composite number $k$ is a prime distance from the nearest primes $\ne k \pm 1$ on either side

Prove that if $k$ is highly abundant or highly composite and $q,p$ are the nearest primes with $q+1<k<p-1$, then $k-q,p-k$ are primes. This immediately implies that all highly abundant and ...
3
votes
2answers
181 views

Efficiently identifying spam honeypots

I realise that the title is computing specific, but I think the underlying problem is general - I just don't know how to phrase it more generally (which may be part of my problem). So I am asking ...
0
votes
2answers
218 views

Prove $\log_a(b)$ is irrational given that $a, b$ are positive distinct primes.

I know this is a classical proof by contradiction exercise, and there are full solutions else where, doing a quick search I didn't find any, but I would approach this question like this: Suppose ...
0
votes
1answer
62 views

Prove that all practical numbers not of the form $2^n$ are pseudoperfect

Prove that all practical numbers not of the form $2^n$ are pseudoperfect. practical - $n$ such that every smaller integer is expressible as a sum of distinct divisors of $n$ pseudoperfect - $n$ such ...
6
votes
1answer
199 views

Prime harmonic series

We have following identity: ($p$ is a prime number) $$\left(1+\frac{1}{p}\right)\sum_{k=0}^n\frac{1}{p^{2k}}=\sum_{k=0}^{2n+1}\frac{1}{p^k}$$ Now, How to derive the following inequality from the above ...
12
votes
2answers
599 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
3answers
170 views

How quickly can we find a prime at least as great as $n$?

This may be trivial, but I'm wondering a few things. Is there an easy way to find a prime of the form $2k+1>n$ for some $n$? EDIT How quickly can we find a prime greater than a given number $n$?
6
votes
1answer
136 views

What is the smallest real $q$ such that there is always a prime between $n^q$ and $(n+1)^q?$

In this answer, it is mentioned that for $q=3$, we are guaranteed the existence of a prime between $n^q$ and $(n+1)^q$, and that it is conjectured that this is true for $q=2$. I am wondering though, ...
4
votes
2answers
126 views

Real numbers as infinte product of primes

We can uniquely write every number in $\mathbb{Q}_+$ as $\prod_{i=1}^{N} p_i^{n_i}$ where $p_i$ is the $i$th prime number and $\{ n_i \}_{i=1}^{N}$ is some finite sequence of indices, with each $n_i$ ...
12
votes
1answer
168 views

What is the significance of the power of $3$ in the sequence of primes given by $\lfloor A^{3^n}\rfloor ?$

Mill's constant is a number such that $\lfloor A^{3^n}\rfloor$ is prime for all $n$. The existence of such an $A$ was proven in $1947$. I know little about number theory, but I am curious as to why ...
2
votes
0answers
48 views

Number of primes of type 4*n +1 in a range

I want to find number of primes which are congruent 1 (mod 4) in a range [a, b]. The range can be of order $10^9$ as a and b can be from $1$ to $10^9$. I tried segmented sieve but for a range so ...
0
votes
2answers
158 views

What is mod(a,b)?

I was reading the AKS Primality Test. AKS. I could not understand the line : $(x - a)^{n} = (x^{n} - a) \pmod{(n,x^{r}-1)}$ What is $\mod{(a,b)}$ in it ?
2
votes
0answers
165 views

Approximation to $\pi(x)$ conjecture.

A friend conjectured that $\left[\prod_{k=1}^{a_j <\sqrt{x}} \left(1-\frac{1}{a_k}\right)\right] x$ is usually closer to $\pi(x)$ than $\operatorname{Li}(x)$ is for some (fixed) sequence of ...
4
votes
2answers
241 views

Proving that $n\mid(nCr)$ for all $r$ ($1 \leq r \leq n-1$), only if $n$ is prime

I'm trying to prove that $n\mid(nCr)$ for all $r$ ($1 \leq r \leq n-1$) if and only if $n$ is prime. Now proving that if $n$ is prime then $n\mid(nCr)$ is pretty easy, but how would you go about ...
1
vote
4answers
71 views

Determining the general form of $10^x \bmod 210$

While solving a problem I came across solving $10^x\bmod 210$ for various values of $x$. It seems that the values repeat after an interval of 6 for $x\geq4$. Can any one explain how can solve this ...
1
vote
1answer
169 views

Divisibility of multinomial by a prime number

What is the condition for divisibility of multinomial $ \dbinom {n}{x_1, x_2, \dots, x_k} $ by a prime $p$? Update: I tried to solve using a generalisation of Lucas Theorem by representing the $n$ ...
0
votes
1answer
95 views

If $K$ and $S$ are prime numbers then how can I prove that for some $n$, there exist prime numbers of the form $K+2n+2$ and $S-2n$?

If $K$ and $S$ are prime numbers then how can I prove that for some $n$, there exist prime numbers of the form $K+2n+2$ and $S-2n$?
6
votes
1answer
270 views

Let $F_n$ be a Fibonacci number and $p$ a prime. Verify that for $p \le 61$, if $p\equiv\pm1 \pmod{5}$ then $p\mid F_{p-1}$

Define the Fibonacci entry point of $p$ to be the least integer $n$ such that $p\mid F_n$ So for example, for $p = 3$ - the Fibonacci entry point is $n = 4$ since $F_4 = 3$ and obviously $3\mid 3$. ...
14
votes
4answers
575 views

Why do repunit primes have only a prime number of consecutive $1$s?

Repunit primes are primes of the form $\frac{10^n - 1}{9} = 1111\dots11 \space (n-1 \space ones)$. Each repunit prime is denoted by $R_i$, where $i$ is the number of consecutive $1$s it has. So far, ...
8
votes
1answer
119 views

Prove that $\forall p \in \Bbb P;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$

Prove that $\forall p \in \Bbb P,n \in \Bbb Z^+;p \ne 5,$ $F_{p^n - \left(\frac{5}{p}\right)p^{n-1}} \equiv 0 \mod p^n$ and $F_{5^n} \equiv 0 \mod 5^n$, where $\left(\dfrac{5}p\right)$ is the Legendre ...
10
votes
6answers
867 views

What are some easy-to-remember prime numbers? [closed]

This is a question without much mathematical value, but since I don't immediately see an answer on Google I thought I'd ask anyway ... I'm looking for some largeish (> 10,000) easy-to-remember primes, ...
1
vote
1answer
198 views

Linear equation with prime coefficient.

Suppose we have a linear equation with two variables say $x$ and $y$ and three integer coefficient $a , b$ and $c$ (constant), where $a$ and $b$ are prime all are greater than zero. $ax+by=c$ how ...
4
votes
1answer
431 views

Let $p$ be a prime and $q$ a prime divisor of $2^{p} -1$. Use Fermat's Little Theorem to prove that $q\equiv 1 (\mod \space p)$

Question continued: Hint: Consider $ord_{q}(2)$. Similarly, prove that if $r$ is a prime factor of $2^{2^{k}}+ 1 $ then $r\equiv1 (\mod \space 2^{k+1})$ I think I have the first part, however I ...
1
vote
2answers
225 views

Twin, cousin, and sexy prime property

Why the digital root of twin primes is always $(2,4) (8,1) (5,7)$? Why the digital root of two primes with difference $4$ is always $(4,8) (1,5) (7,2)$?
1
vote
2answers
114 views

Problem of Ages (Problema das Idades)

English: Somebody help me with this challenge? It's very confusing: Today, both me and my younger brother are between $10$ and $20$ years old. Also, our ages are expressed by prime numbers and the ...
1
vote
0answers
51 views

What is the signifigance of prime numbers [duplicate]

A buddy of mine said that prime numbers are valuable and people will actually pay for new, undiscovered prime numbers. He said people build computers that specifically just "mine" for prime numbers. ...
2
votes
1answer
94 views

Between Mertens' theorems

It is well-known that $$ \sum_{p\le x}\frac{\log p}{p}=\log x+O(1) $$ and $$ \sum_{p\le x}\frac1p=\log\log x+M+o(1). $$ What is the order of $$ \sum_{p\le x}\frac{\sqrt{\log p}}{p} $$ ?
0
votes
1answer
108 views

Theorem on Sum of prime factors

Robin's theorem gives an inequality for the divisor function of a number. Is there an equivalent theorem where we have an inequality for the sum of the prime factors of that number instead of the ...
1
vote
0answers
88 views

Prime Numbers and Primitive Roots

Let $p_1$, $ p_2$, $p_3$ different prime numbers. Let $N = p_1p_2p_3$. Given $(p_1-1)|(N-1), (p_2-1)|(N-1)$ and $(p_3-1)|(N-1)$, prove that for every number $a \in \Bbb N$ such that $\gcd(a,N) = 1$ ...