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
votes
0answers
77 views

Goldbach conjecture related thinking

Background The sequences $a_k = 2(p-1)k + p$ yield many prime numbers when $p$ is a prime number. (Test it) $2p \equiv 2 \bmod{(2p-2)} \equiv 2 \bmod {(2(p-1))}$ Direction Following from ...
6
votes
1answer
143 views
+50

Test about prime gaps: which conclusions can be drawn from the results?

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$ ...
7
votes
0answers
55 views

What do we know about the first occurrences of prime gaps?

Are there any conjectures from which we can infer something about the first occurrences of prime gaps length $n$ and their distribution? I've made an interesting graph of these values to make this ...
0
votes
1answer
23 views

question about first occurring prime gaps

If a prime gap $g(p)$ is the first occurring prime gap of it's size, does this imply that it is also the largest gap below $p$? In other words, is the set of first occurring prime gaps contained ...
3
votes
2answers
58 views

Indexes of prime Fibonacci numbers

I found this on Mathworld, but I can't seem to find any proof, either on StackExchange, nor any other site: Why do all Fibonacci primes, except for $F_4=3$, have prime indexes (with $F_0=0$)? My ...
4
votes
2answers
81 views

Why is it that the product of first N prime numbers + 1 another prime? [duplicate]

Recently I came across this proof for fact that primes are infinite. It's a proof by contradiction. The proof assumes that primes are finite and there is a prime M which is larger than any prime out ...
1
vote
1answer
28 views

Fermat primality test and Fermat pseudoprime

What is the difference between Fermat primality test and Fermat pseudoprime?Can anyone explain me how we use them ?
23
votes
2answers
547 views

Is $1992! - 1$ prime?

Consider the factorials, defined inductively by $1! = 0! = 1$ and $n! = n\cdot(n-1)!$ for $n \geq 2$. Question: Is $1992!-1$ a prime number? The question is from a book, maybe is contest math ...
0
votes
0answers
64 views

Sets with $n$ prime 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\}$$ ...
1
vote
1answer
58 views

Why does symmetry happen in reset-based random walks?

Studying the basic concepts about random walks / brownian motion, and based on the idea of a Möbius-based walk in Wolfram's website, I wanted to try my own version of it in Python to compare it with ...
10
votes
5answers
5k views
0
votes
1answer
36 views

Prime Number Algorithm

function isPrime(n) { // If n is less than 2 or not an integer then by definition cannot be prime. if (n < 2) {return false} if (n != Math.round(n)) {return false} // Now assume that n is ...
20
votes
5answers
2k views

Are primes randomly distributed?

There is a famous citation that says "It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990) I have this very ...
0
votes
0answers
73 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. Here is the definition: $\forall n=1+2k,\quad k\ge5,\quad k \in \mathbb N, \quad \exists$ $p ...
2
votes
1answer
63 views

Is the Green-Tao theorem valid for arithmetic progressions of numbers whose Möbius value $\mu(n)=-1$?

I am reading the basic concepts of the Green-Tao theorem (and also reading the previous questions at MSE about the corollaries of the theorem). According to the Wikipedia, the theorem can be stated ...
2
votes
2answers
508 views

Show that $n!+1$ has a prime factor $\;>n$; showthat there are infinitely many primes

I don't know how to prove this and it's really bugging me. Thanks to anybody that can help! Let $n$ be any natural number. Prove that $n! + 1$ contains a prime factor greater than $n$ and use that to ...
5
votes
2answers
246 views

Inequality involving a product over the primes

Is there someone who is able to prove the following statement? $$\prod_{m=1}^n \dfrac{p_m-1}{p_m} \leq \dfrac{1}{\ln(n)}$$ for all integers $n >1$ where $p_m$ is the $m$-th prime number.
1
vote
0answers
23 views

Calculating $n$-th $q:P(q)=p \in \Bbb P$

Let $P(x)$ denote the number of ways of writing an integer $x$ as a sum of positive integers (where permutation of the array of integers in the sum doesn't count). Ex: $P(1)=1, P(2)=2,P(4)=5$. Let ...
25
votes
3answers
393 views

Can a number be equal to the sum of the squares of its prime divisors?

If $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then define $$f(n):=p_1^2+\cdots+p_k^2$$ So, $f(n)$ is the sum of the squares of the prime divisors of $n$. For which natural numbers $n\ge 2$ do we have ...
1
vote
2answers
74 views

The product of two prime numbers

I have two expressions (both of which have a term raised to the power of $n$) and I am trying to prove that they can't be prime numbers at the same time for $n>2$. I can't post the expressions, ...
1
vote
2answers
31 views

Is there a method to determine a prime number containing the first n digits?

For example, the number $10243$ is prime and contains the digits '0,' '1,' '2,' '3,' and '4.' Similarly, the number $20143$ is prime. Is there a method to determine whether a prime number exists ...
1
vote
3answers
27 views

Finding all the divisors of $a$ by decomposing it into the product $p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdots p^{\alpha_r}_{r}$

I'm trying to prove the following statement regarding the fundamental facts of prime numbers, but I don't really understand the relationship between $a$ and $b$. In order to find all the divisors ...
9
votes
2answers
422 views

Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
4
votes
0answers
62 views

What is the next prime with this form? [duplicate]

The following are primes, $$P_1 = 2^2 + 3^3$$ $$P_2 = 2^2 + 3^3 +5^5 + 7^7$$ After these two, the only prime of such form I've found is, $$P_3 = 2^2 + 3^3 + 5^5 + 7^7 + 11^{11} + 13^{13} +\dots+ ...
5
votes
2answers
133 views

Is $a=\frac{1992!-1}{3449\times 8627}$ a prime number?

Is $a=\dfrac{1992!-1}{3449\times 8627}$ a prime number ? This is a natural follow-up to that recent MSE question We know that $a$ has $5702$ digits and no prime divisor $<10^6$.
0
votes
2answers
64 views

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

The twin prime conjecture states basically 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 ...
0
votes
0answers
75 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 ...
7
votes
2answers
352 views

Efficient way to compute $\sum_{i=1}^n \varphi(i) $

Given some upper bound $n$ is there an efficient way to calculate the following: $$\sum_{i=1}^n \varphi(i) $$ I am aware that: $$\sum_{i=1}^n \varphi(i) = \frac 12 \left( 1+\sum_{i=1}^n \mu(i) ...
7
votes
6answers
1k views

what is Prime Gaps relationship with number 6?

Out of the 78499 prime number under 1 million. There are 32821 prime gaps (difference between two consecutive prime numbers) of a multiple 6. A bar chart of differences and frequency of occurrence ...
0
votes
3answers
509 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 ...
-2
votes
1answer
19 views

inequality on Gaussian prime

Consider any Gaussian prime $p$ (except $|p|=\sqrt{2}$). If we have $|x|\leq|p|+0.5$, where $x$ is a nonzero Gaussian integer, can we prove $|x|\leq|p|$?
3
votes
0answers
54 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 also reviewed here at MSE former questions to learn more. While reviewing the questions and answers, I found references to the Fibonacci ...
-2
votes
0answers
43 views

Summation of prime multiples less than n [on hold]

How can I sum the following $$ \sum (2^x\cdot3^y\cdot5^z\cdot7^w\cdot\prod_1^m(p_i^{a_i})) $$ with $$2^x\cdot3^y\cdot5^z\cdot7^w\cdot\prod_1^m(p_i^{a_i}) \le n$$ where $p_i \ge 11$ are list of fixed ...
0
votes
3answers
58 views

The square of n+1-th prime is less than the product of the first n primes.

I wanted to prove the following question in an elementary way not using Bertrand postulate or analytic estimates like $x/\log x$. The question is $$ p_{n+1}^2<p_1p_2\cdots p_n,\qquad(n\geq4) $$ I ...
2
votes
0answers
95 views
+50

A lower bound for an arithmetic function

Let $N \in \mathbb{N}$ such that $\phi(N) \sim N$, where $\phi$ is the Euler's totient function. Let $A \subset [N] := \{1, 2, \ldots, N\}$. For $n \in \mathbb{N}$ define the function $$ C_A(n) = \#\{ ...
2
votes
1answer
56 views

How to show $n$ is a prime number?

Let $a$ and $n$ be integers greater than 1. Suppose that $a^n-1$ is a prime. Show that $a=2$ and $n$ is a prime. What can you say about primes of the form $2^n+1$? By ...
1
vote
0answers
49 views

Are logarithms of prime numbers algebraically independent?

From Baker's theorem it follows that a linear combination of natural logarithms of prime numbers with non-zero algebraic coefficients can never be zero. Has it been proved that the set of all natural ...
8
votes
1answer
988 views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
1
vote
3answers
62 views

Upper bound for prime-counting function: $ \pi(n)\le\frac{n}{3}+2 $

$ \pi(n)\le\frac{n}{3}+2 $... Could someone explain me, how to prove it? I'm completely stuck, as informations I found on Wikipedia aren't very clear to me. (I was able to prove that for sufficiently ...
6
votes
3answers
183 views

Show that prime $p=4n+1$ is a divisor of $n^{n}-1$

Show that the prime number $p=4n+1$ is a divisor of $n^{n}-1$ Ok, the question itself is simple as hell, but I couldn't think of a simple way to solve this question. I tried to solve the ...
6
votes
2answers
312 views

Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every ...
0
votes
0answers
15 views

Prove that if $\ p^2 = a^2+2b^2 $ then $\ p = m^2+2n^2 $ (where a, b, m, n are integers, and p is prime) [duplicate]

Given that $\ p^2$ can be written in the form $\ p^2=a^2+2b^2 $ (where a & b are integers, and 'p' is a prime number), then prove that the prime number 'p' can also be written in the form $\ ...
-9
votes
0answers
45 views

2,1,3,5,7=???????? i need help plz [closed]

I cannot figure this out! I know nothing about prime numbers in sequence anymore. Ive been out of school for a long while now.
6
votes
3answers
71 views

sequence of primes in arithmetic progression

The question is: Suppose $p_1<p_2<...<p_{15}$ is a sequence of prime numbers in arithmetic progression, with common difference $d$. Prove that $d$ is divisible by $2,3,5,7,11$ and $13$. Let ...
0
votes
1answer
33 views

Wieferich prime-Lang-Trotter conjecture connection?

Crandall-Dilcher-Pomerance prediction states that the number of Wieferich primes $<x$ is $log\ logx $ N.Katz in "WIEFERICH PAST AND FUTURE" states; The Crandall-Dilcher-Pomerance prediction is ...
30
votes
2answers
432 views

Proving that if $p^2 = a^2 + 2b^2$ then also $p$ can be written in form $a^2 +2b^2$

I'm high school student, and this problem has bothered me for about 2 weeks now. I don't necessarily need a solution, but for example mentioning a helpful theorem or property that could help me to ...
1
vote
2answers
36 views

Property of additive group [closed]

Let $m \in \mathbb{Z}_q$, for a prime $q$ and $x \in \mathbb{A}$, where $\mathbb{A}$ is an additive group of order $q$. Then is it always true that $mx \in \mathbb{A}$? If true, how to prove it? ...
1
vote
2answers
57 views

How many number id divisible by $p$ and is not divisible by any primes number which is less than $p$?

Let $N$ be a big integer. Let $p$ be a prime number. Is there a formula to count how many number less than $N$ such that they are divisible by $p$ and not divisible by any prime less than $p$. For ...
25
votes
1answer
289 views

Fibonacci $\equiv -1 \mod p^2$

Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify. EDIT: In response to ...
2
votes
1answer
154 views

Ulam spiral and triangular numbers

Is there any explanation for the twister-like pattern build by triangular numbers $$\Delta_n = \frac{n\cdot(n+1)}{2}$$ in the Ulam Spiral? Here for $1,\ldots,100$: Here's a picture with many more ...