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

Unusual behavior of 210 and 199 regarding prime numbers

Adding 210 to 199 over and over again, you get 8 more primes that can be arranged together into a 3x3 magic square: 1669 199 1249 619 1039 1459 829 1879 409 Is there any other pairs of numbers ...
41
votes
5answers
4k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
3
votes
1answer
84 views

Golden Ratio of Primes (Amateur)

Unable to find information elsewhere, so I'll try here. What two consecutive primes are closest to producing the Golden Ratio? Or two of any Primes? Has this been determined? Thanks!
0
votes
1answer
86 views

Public and private RSA keys, using the primes $p = 5$ and $q = 11$

Assume that $p = 5$ and $q = 11$, and all other variables are defined as per the RSA theorem (a) Suppose we consider $e = 3$. Would $(e, n)$ be a suitable public key? (b) Prove that if $d = 27$, ...
0
votes
2answers
52 views

Dividing a product of different primes by another prime

A relatively straight forward question. If I were to multiple any amount of different prime numbers together say 7*3*11, is it possible to divide the product by a single other prime number say 23 and ...
14
votes
3answers
880 views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime A ...
1
vote
1answer
33 views

Given a sequence, construct a function whose integral is equal to the sum of the sequence

Let $P_n$ be the sequence of prime numbers, where $P_0=2$. Given $m\in\mathbb{N}$, how can we construct $f(x)$ such that: $\displaystyle\forall{0}\leq{i}\leq{m}:f(i)=P_i$ ...
1
vote
2answers
273 views

Divisibility in a recurrent sequence

Let $a_1=0$, $a_2=\alpha$, and $a_n=\lambda a_{n-1}+\mu a_{n-2}$ for $n\geq 3$. Are there positive integers $\alpha$, $\lambda$, $\mu$ such that $$a_{p^2} \equiv 0 \mod p $$ for every prime ...
2
votes
3answers
53 views

Smallest prime factor of a Mersenne number

The Mersenne numbers $M_n$ are integers of the form $2^n-1$, where $n$ is a positive integer. In the case when $n$ is a prime, are there any results known on the smallest prime factor, $p_n$, of ...
11
votes
7answers
6k views

Is a prime factor of a number always less than its square root?

I was going through the fundamental theorem in Number Theory where any non zero integer n can be represented as a product of distinct primes. A related problem with this theorem is to prove that for ...
2
votes
1answer
38 views
3
votes
0answers
38 views

Are there infinitely many prime numbers in $a_n=\frac{7\times 10^n-1}{3}$?

In the array $a_n=\frac{7\times 10^n-1}{3}$, are there infinitely many primes? (when $n={7+16k},a_n$ is divisible by $17$, so there are infinitely numbers not prime)
3
votes
1answer
69 views

Possible Prime Sum Pattern (Amateur)

Disclaimer: I’m an amateur, and have no advanced knowledge of math, so please forgive my ignorance as I’m just curious to know if I’ve stumbled upon something or not. Prime Numbers: 2, 3, 5, 7, 11, ...
3
votes
1answer
38 views

Additive group contains exactly three elements of the set $\{p,p+q,pq,p^q,q^p\}$

Let $p$ and $q$ be distinct primes. There is a proper subgroup $J$ of the additive group of integers which contains exactly three elements of the set $\{p,p+q,pq,p^q,q^p\}$. Which three elements are ...
2
votes
1answer
31 views

The contrapositive of “if $x$ is even and $x$ is greater than $2$, then there exist prime numbers $p$ and $q$ such that $x = p + q$”

Proposition: If $x$ is even and $x$ is greater than $2$, then there exist prime numbers $p$ and $q$ such that $x = p + q$. Contrapositive: If for all prime numbers $p$ or $q$, $x$ does not equal $p + ...
6
votes
1answer
142 views

Does $\sum\limits_{n=1}^{\infty}\frac{1}{P_n\ln(P_n)}$ converge to the golden ratio?

The sum $\displaystyle\sum\limits_{n=2}^{\infty}\frac{1}{n\ln(n)}$ does not converge. But the sum $\displaystyle\sum\limits_{n=1}^{\infty}\frac{1}{P_n\ln(P_n)}$ where $P_n$ denotes the $n$th prime ...
3
votes
0answers
80 views

conjecture about prime numbers and distance between them

is there a name for this conjecture? Conjecture: given $p_n$ a prime number sequence where $p_1=2,p_2=3,\cdots$, then for all $n\in\mathbb{N}^*$ and $k\in\mathbb{N}$, holds that $\displaystyle ...
0
votes
4answers
121 views

How do you go about finding a 12 digit prime number?

How do you go about finding a 12 digit prime number?
2
votes
2answers
31 views

Proof that if $k$ is the highest factor of any positive integer $n$ such that $k<n$, then $n/k$ is prime

It's straightforward to say that when $n$ is prime, $k=1$ since $k$ must be less than $n$. For the case where $n$ is not prime, I thought proving that the lowest factor of $n$ is prime would be the ...
4
votes
1answer
105 views

Elementary proof there are infinitely many primes of the form $4n+1$

My attempt: $4n+1$ is odd. Thus its decomposition must not contain $2$. Every odd number is either of the form $4k-1$ or $4m+1$. $(4m+1)(4k-1)$ is never of the form $4n+1$. So $4n+1$ has factors ...
0
votes
1answer
34 views

Calculate total number of matrices of all orders which contain $2013$ elements

Calculate total number of matrices of all orders which contain $2013$ elements My Try:: By Simple Guessing wecan say that there are two matrices of order $(1\times 2013)$ and $(2013 \times 1)$ ...
0
votes
1answer
117 views

Primes and the number of digits of the prime [duplicate]

Say $n$ has $k$ decimal digits, all of which are ones. How would you show that if $n$ is prime, then $k$ is prime?
1
vote
1answer
35 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
-1
votes
0answers
37 views

Happy prime equation

I read that a happy number is: A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and ...
0
votes
2answers
39 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
1
vote
0answers
45 views

Sequence of primes by concatenating digits in a given base.

Given a base, $b$ is there is a sequence $\lbrace a_n\rbrace_{n\geq 0}$ where $a_k \in \lbrace 1,2\cdots, b-1\rbrace$so that the sequence: $$b_n:= \sum_{k=0}^n a_kb^k$$ is a sequence of primes ...
4
votes
1answer
146 views

Squeezing $\pi(x)$ out of $\psi(x)$

Can $\pi(x)$ be written in terms of $\psi(x)$? I can only seem to approximate it: $$ ...
1
vote
0answers
33 views

A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bears some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
4
votes
1answer
55 views

Meaning of Rays in Polar Plot of Prime Numbers

I recently began experimenting with gnuplot and I quickly made an interesting discovery. I plotted all of the prime numbers beneath 1 million in polar coordinates such that for every prime $p$, ...
3
votes
1answer
95 views

Why is $p_n\sim\sum_{k=1}^{n}\log(p_k)$?

Why is $$ p_n\sim\sum_{k=1}^{n}\log(p_k) $$ where $p_n$ is the $n$th prime? In addition, is it true that $$ n\log\left(\dfrac{\sum_{k=1}^{n}\log(k)}{\log(\log(n))}\right) $$ is a better ...
3
votes
0answers
55 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 4

Following a previous question (here you'll find an introduction): A paper by Maier which refutes Cramer's Model suggests we should replace the heuristic "$\Bbb P(n\in\mathcal P)=1/\log n$" with ...
2
votes
1answer
252 views

is it possible to get the Riemann zeros

since we know that the number of Riemann zeros on the interval $ (0,E) $ is given by $ N(E) = \frac{1}{\pi}\operatorname{Arg}\xi(1/2+iE) $ is then possible to get the inverse function $ N(E)^{-1}$ ...
1
vote
0answers
43 views

Fast algorithm for generating consecutive primes larger than N

I'm looking for a fast algorithm to generate primes larger than a random 4096 bit number $N$. I know about the Sieve of Atkin, but AFAIK it can only be used to find all primes up to a certain limit. ...
1
vote
2answers
111 views

RSA - finding $p$ and $q$

If the public key $(e,n)$ and the private key $(d,n)$ are known, how can I find the $p$ and $q$ primes by the easiest way? When $n$ and $\varphi(n)$ are given was easy to solve, but this issue I can't ...
0
votes
2answers
216 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
1
vote
0answers
25 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 3

Following a previous question (here you'll find an introduction): The book states that almost surely $$\pi_S(x+y)-\pi_S(x)=\mathrm{li}(x+y)-\mathrm{li}(x)+O(\sqrt y)$$ as soon as $y/(\log ...
2
votes
0answers
40 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 2

Following a previous question (here you'll find an introduction): The book states that using the convergence of the binomial distribution towards the Poisson distribution, it's easy to show that ...
9
votes
0answers
239 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 1

I was reading "The Prime Numbers and Their Distribution" by Gérald Tenenbaum and Michel Mendès France, the section about Cramér's Model, and I couldn't prove a couple of results. I would like to start ...
2
votes
1answer
67 views

Finding an $n$ such that $n^2 \equiv -1 \mod p$

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists? Is there anything better than the brute-force approach up to $p-1 ...
0
votes
1answer
64 views

Probability with Primes

What is the probability that a positive divisor of $8748$ million is the product of exactly $20$ non-distinct primes? To try and solve this question I split up $8748$ into $2^8 \cdot 5^6 \cdot 3^7 $ ...
1
vote
4answers
149 views

Why didn't Fermat provide proofs of his theorems?

Apparently Fermat stated but didn't provide proofs of various theorems named after him, including Fermat's little theorem, Fermat's theorem on sums of two squares, Fertmat's polygonal number theorem, ...
1
vote
2answers
43 views

Can't understand source of constant for prime counting function:

Consider the prime counting function $$ \pi(x) = \ the \ number \ of \ primes \ less \ than \ or \ equal \ to \ x$$ It is well known due to the sieve eratosthenes that given an integer $n$ and the ...
33
votes
6answers
2k views

Is $2^{218!} +1$ prime?

Prove that $2^{218!} +1$ is not prime. I can prove that the last digit of this number is $7$, and that's all. Thank you.
0
votes
1answer
153 views

Let $x = 2441921$. Factor $x$ into a product of primes.

Let $x = 2441921$. Factor $x$ into a product of primes. I found that: $1519^2 −x=−134560= −2^5 ·5 · 29^2$ and $1541^2 −x=−67240= −2^3 · 5 · 41^2$. I am trying to figure out what to do from here. ...
-4
votes
1answer
76 views

Please give feedback to this solution.

Consider the number $n= 2^{1000000000000000000000000000000000} +1$. Suppose that it is known that none of the numbers $1 < k < n - 10^{6}$ divides $n$. Does it follow that $n$ is a prime ...
1
vote
3answers
46 views

First index of number in that arithmetic progression which is a multiple of the given prime number

I have a prime number $p$, an arithmetic progression starting at $a$ with common difference $d$. How to find the first index of a term in that arithmetic progression which is a multiple of the given ...
31
votes
6answers
5k views

Are all prime numbers finite?

If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid ...
0
votes
1answer
37 views

Probability and Prime Numbers

What is the probability that a positive divisor of 8748 million is the product of exactly 20 non-distinct primes?
4
votes
0answers
52 views

Euler's proof of divergence of sum of reciprocals of primes

On Wikipedia at link currently is: \begin{align} \ln \left( \sum_{n=1}^\infty \frac{1}{n}\right) & {} = \ln\left( \prod_p \frac{1}{1-p^{-1}}\right) = -\sum_p \ln \left( 1-\frac{1}{p}\right) \\ ...
0
votes
2answers
69 views

Represent a prime number $p$ congruent to $1$ $\pmod{3}$ by a sum of a square and $3$ times a square

I want to have a proof of the fact that each prime number is the sum of a square and three times a square (Euler). Context I read the answer to my former question about the number of points on an ...