Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [prime-numbers]

Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

0
votes
1answer
20 views

Matrix and powers

Let $A \in M_2(\mathbb{C})$ a matrix which does not have all the elements real. Let $p$,$q\in \mathbb{N}$, $(p,q)=1$ such that $A^p$ and $A^q$ have all the elements real. Find $A^2$. Any ideas for ...
0
votes
3answers
61 views

What will accepting 1 as prime change?

How significant is the fact 1 isn't a prime number? What will happen if it is? What areas of Mathematics are affected by changing the fact? I know why and how 1 isn't a prime. My question is how ...
2
votes
1answer
66 views

Why Proof of Work is Hard

I am finally beginning to understand how Proof of Work (PoW) works, and am wondering briefly why it is considered "hard" mathematically to solve. The whole goal of it (it sounds like) is for it to ...
1
vote
0answers
58 views

“Exceptional” primes greater than 2

In many theorems, the prime $2$ has an exceptional characteristic. But where can other primes be exceptional? As a couple examples: 1) In the Fibonacci sequence $5$ is exceptional because $p=5$ ...
1
vote
1answer
63 views

Find all primes $p$ for which there are positive integers $x, y$ such that $p+1=2x^2$ and $p^2+1=2y^2$ [duplicate]

Find all primes $p$ for which there exist positive integers $x, y$ such that $p+1=2x^2$ and $p^2+1=2y^2$. I have tried coming up with an equation for $p$ or $p^2$ and this is what I've got $p=2x^2-1$...
2
votes
1answer
42 views

Question related to derived formula for zeta-zero counting function

I've been attempting to derive a zeta-zero counting function based on the distributional or Fourier series representation of the second Chebyshev function $\psi(x)$ or its first-order derivative $\psi'...
1
vote
0answers
38 views

Can prime density be increased by arranging odd integers in colums? [on hold]

Odd integers can be arranged in increasing numbers of columns. For 1 column the kth element is $2k+1$ and for three columns $6k+1, 6k+3$ & $6k+5$. The middle column cannot contain any primes. ...
2
votes
0answers
37 views

Density of integers $n$ with all prime factors of order $O(\log n)$?

For a rational integer $n \in \mathbb{Z}_{+}$, let $\mathfrak{p}(n)$ denote the set of (distinct) prime factors of $n$. Then for a positive constant $c$, let $$f(x) = \vert\{n\in\mathbb{Z}_{+}:\ n\...
1
vote
1answer
51 views

Since $\lim_{n\to\infty}\pi(n) = \frac{n}{ln(n)}$, can't this be used to prove Legendre’s conjecture?

Legendre's conjecture states that for all $n$, there is a prime number between $n^2$ and $(n+1)^2$. It has been proven that $\lim_{n\to\infty}\pi(n) = \frac{n}{\ln(n)}$. It can be proven that $\...
0
votes
3answers
338 views

Alternate definition of prime numbers

The prime numbers are usually defined to be positive integers with exactly two distinct divisors—one and the number itself. There are plenty of variations on this definition. Just out of sheer ...
2
votes
0answers
45 views

Convergence of $\sum\limits_p \frac{\chi(p)}{p}$ and the prime number theorem

Consider the sum $$\sum\limits_p (-1)^{\frac{p-1}{2}}\frac{1}{p}=-\frac{1}{3} + \frac{1}{5} - \frac{1}{7} - \frac{1}{11} + \frac{1}{13} + \frac{1}{17} - \cdots \tag{1}$$ of signed reciprocals of the ...
29
votes
1answer
2k views

Are prime numbers really random?

While practicing to code for my college course I stumbled upon this and would like to know if this is something new or significant as I haven't found anything resembling it on the internet. Let $p_i$ ...
11
votes
0answers
192 views

Why is counting the number of least prime factors of a sequence of consecutive integers insufficient to resolve Legendre's Conjecture?

I've been thinking a long time about Legendre's Conjecture. A few nights ago, I came across the following argument which is of course too simple to be true. I would greatly appreciate if someone ...
2
votes
2answers
86 views

Two Subsets of Squares of Reciprocals of Primes with Equal Sums

Let $$A=\{\frac{1}{2^2},\frac{1}{3^2},\frac{1}{5^2},...\}$$ be the set of squares of the reciprocals of prime numbers. We have $$\sum_{x\in A}x < \infty$$ Do there exist $B \subset A$, $C \subset ...
2
votes
1answer
110 views

Is $10^{2^{21}}+1$ known to be composite?

I looked at the generalized Fermat-prime-numbers. According to factordb, the case $$10^{2^{21}}+1$$ is unknown. Neither a factor is displayed nor $C$ for "composite". Hence my question : Is $$10^{2^...
1
vote
1answer
34 views

Error in counting the number of relatively coprime integer pairs less than N

The number of relatively coprime integers less than $N$ grows like $\frac{N^{2}}{\zeta(2)}$ (which, looking at the structure of $\frac{1}{\zeta(2)}=\Pi_{p_{k}}(1-\frac{1}{p_{k}^{2}})$, can be proven ...
0
votes
2answers
30 views

How to calculate divisibility with 3 of a ratio?

Given the equation $k = (p - 1)/2$ where $p$ is any prime number, what is the chance that a randomly chosen element from the set of all $k$s will be divisible by 3? Or rather, how can this probability ...
2
votes
0answers
35 views

Questions Related to the Monster Group Size

Assume the term $\phi$-reduction refers to recursive application of Euler's totient function $\phi(n)$ as follows until the result $1$ is reached. $\quad\phi_0(n)=n$ $\quad\phi_1(n)=\phi(n)$ $\quad\...
3
votes
2answers
66 views

Proof Explanation - Odd prime division

Prove that if $p$ is an odd prime, then $$p\mid \lfloor(2+\sqrt5)^p\rfloor - 2^{p+1}$$ The solution posted by another user is as follows: Let $𝑁=(2+\sqrt5)^p + (2-\sqrt5)^𝑝$. Note that $N$ is an ...
-1
votes
6answers
77 views

Prove that if $a^2$ is divisible by $5$, then a is divisible by $5$.

How can I prove this? Prove that if $a^2$ is divisible by $5$, then a is divisible by $5$.
-1
votes
0answers
40 views

Evaluate $\lim_{n\to\infty}\prod_{k=n} ^\infty \frac{(p_k-2)}{p_k}$ [closed]

How do you evaluate this infinite product of primes? $$ \lim_{n\to\infty}\prod_{k=n} ^\infty \frac{(p_k-2)}{p_k}$$
0
votes
1answer
43 views

Elementary Proof of Erdos for prime number theorem.

Where can I find a good proof that has a good and elementary explanation? I've googled it, but what I found is not exact and complete. I want a complete proof without any referencing.
-1
votes
1answer
73 views

What do mathematicians mean when they say “we don't know how to predict which numbers are primes”?

one of the key goals of number theory is to understand prime numbers, in particular, to predict which numbers are prime and which are not. If we would know the exact function $\pi(x)$ which denotes ...
1
vote
3answers
46 views

Can $x^n-(x-1)^n$ be Prime if $n$ is Not Prime?

I'm hoping someone can provide an answer or a link to a proof regarding this question.
3
votes
1answer
52 views

When will a prime element of $\Bbb{Z}[(\sqrt{5}-1)/2]$ have field norm equal to a rational prime?

Consider the integer ring of $\mathbb{Q}[\sqrt{5}]$, i.e. $\mathbb{Z}[(\sqrt{5}-1)/2]$. Then if $N(x)$ denotes the field norm of $x\in\mathbb{Z}[(\sqrt{5}-1)/2]$, then $N(x) = p$ for a rational prime $...
3
votes
1answer
100 views

How many prime numbers contain strictly increasing digits?

This was posed as an estimation problem - I'd be interested in both more accurate approximate methods (than my underestimate of 74 in the answer below) and a check of my exact answer (100, already ...
0
votes
1answer
46 views

Primes that give different residue modulo $6$

Let $n>2$ be a natural number. Prove that there exist two different prime numbers $p,q<\frac{n}{2}$ which don't divide $n$ such that $p\not\equiv q<6>.$ My attempt: if $n$ is ...
0
votes
1answer
19 views

What is the correct definition of a Cunningham chain of length $n$?

According to Wikipedia, A Cunningham chain of the first kind of length n is a sequence of prime numbers $(p_1, \ldots, p_n)$ such that for all $1 ≤ i < n, p_i+1 = 2p_i + 1$. Hence each term of ...
0
votes
0answers
62 views

Who was the first person to prove that only primes of the form $4k+1$ can evenly divide odd integers of the form $n^2+1$?

I am writing a paper and I want to cite the person(s) who proved that only primes of the form $4k+1$ can evenly divide odd integers of the form $n^2+1$. Edit: added "odd" For example, if $n=8$, then ...
1
vote
1answer
65 views

A prime number of the form $10^n+1$ [closed]

Find all positive integers $n$ and prime $p$ such that $$10^n+1=p$$
3
votes
1answer
49 views

How to prove that there are infinitely many primes of form $6n+1$? [duplicate]

We know that all primes greater than $3$ are of form $6n+1$ or $6n-1,$ but how do I prove that there are infinitely many of the form $6n+1$? Please prove it without Dirichlet's theorem. Note: This ...
4
votes
3answers
69 views

Prove $\forall n\in\mathbb{N}$, $\exists m\in\mathbb{N}$ s.t. $m>n$ and $m$ is prime [duplicate]

There are two parts I am having trouble getting started. A. Prove that $n_1, n_2,...,n_k\in\mathbb{N}$ are each at least $2$ then $n=n_1n_2...n_k+1$ is not divisible by any numbers $n_1, n_2,...,n_k$....
2
votes
0answers
47 views

Divisibility of Determinant of matrix

Let $p$ be an odd prime number and $T_p$ be the following set of $2\times 2$ matrices $$ T_p= \biggl\{A = \begin{bmatrix}a & b\\c & a\end{bmatrix} \,\Big\vert\: a,b,c \in \{ 0, 1, 2, ... p-1\...
3
votes
1answer
62 views

How to provide a counterexample for if $n$ is prime, then $2^n -1$ is prime

I have the following question where I need to provide a counterexample if $n$ is prime, then $2^n -1$ is prime The statement is invalid and I now that $2^n -1$ is not prime when $ n = 11$, but ...
4
votes
1answer
39 views

Counting 4-digit combinations such that the first digit is positive and even, second is prime, third is Fibonacci, and fourth is triangular

This seemed like a basic problem, but for some reason I can't figure it out: In a $4$-digit combination, the first digit has to be a positive even number, the second a prime number, the third a ...
2
votes
1answer
74 views

Primes $p=n^6+1$

Which is the least odd prime $p=n^6+1$ for some $n\in\mathbb N$? I have tested for $n\leq 10,000$ without finding any. Due to a conjecture of Bunyakovsky there are an infinite number of such primes, ...
2
votes
3answers
56 views

Proof of infinitude of the number of primes of the form $4k+1$

Would this work? If the number of primes of a given form is finite, then the number $$M = (4k_1 + 1)(4k_2 + 1) \ldots (4k_n + 1) + 4$$ should be composite. But the product of numbers of the form $4k +...
0
votes
0answers
44 views

divisibility of the sum of two consecutive primes

For even integers half are divisible by 4, one-third by 6, and one-quarter by 8. For the sum of two consecutive primes, can one say that the divisibility follows the same ratios for division by all ...
1
vote
2answers
39 views

Extension on my one of previous questions about each element in a sequence being coprime. [duplicate]

So my previous question states that: We are given the sequence $𝑘_{n}= 6^{({2}^n)} + 1$. We must prove that the elements of this sequence are pairwise co-prime, i.e prove that if m ≠ n then $𝑔𝑐𝑑(𝑘...
0
votes
0answers
14 views

Lower bound for the ratio of primes and semiprimes as summands

Chen's theorem states that every large enough even integer is the sum of a prime and an almost prime, i.e. an integer that is either a prime or the product of two primes. As there are $s(n):=\pi(2n)-\...
1
vote
1answer
65 views

for all $n \in {N} : a^n + n | b^n +n$

$a$ and $b$ $\in {N^*}$ : for all $n \in {N} : a^n + n | b^n +n $ We suppose that $a$ and $b$ are different . p is a prime number : $gcd(a-b,p)=1$ 1) we can easily show that $ m = p(1+a) - a$ is a ...
1
vote
1answer
80 views

Proving infinite primes [duplicate]

So it's a different take on proving there are infinite primes Given a sequence where any two terms in the sequence are pairwise coprime with each other, how can you prove there are an infinite number ...
1
vote
2answers
48 views

Finding primes from 6 integers closest to two twin primes multiplied together.

We are given the twin primes $a$ and $b$, where $a > 5$. We are told that only one of the following: $ab-3, ab-2, ab-1, ab+1, ab+2, ab+3$ will sometimes generate a prime but not always. It's ...
1
vote
2answers
45 views

Proof for a prime number equation

Let x and n be positive integers such that $$1 + x + x^2 + x^3 ... + x^{n-1}$$ is a prime number. Then show that n is a prime number. So I have summed up the GP and equated it to y which is a prime ...
2
votes
0answers
46 views

Nested Mersenne Primes

A Mersenne Prime is any prime number of the form $2^n-1$, where $n$ is a positive integer. We can trivially see that for any Mersenne Prime $p=2^n-1$, $n$ has to be prime, as if $d \mid n$ and $1<d&...
1
vote
2answers
31 views

Question on Identifying Prime Factors of a Very Large Number

Let $P$ be the product of all numbers less than $90$. Find the largest integer $N$ so that for each $n∈$ {$2,3,4,...,N$}, the number $P+n$ has a prime factor less than 90. Upon first thinking about ...
1
vote
3answers
154 views

Patterns in twin primes

Hi guys so I was reading this question in an old textbook Given a pair of twin primes, a and b both are prime and b = a + 2 So when a > 5 So for example, a = 149 and b = 149 + 2 = 151 The ...
20
votes
3answers
3k views

Why is Sesame Street's Count von Count's favorite number $34,\!969$? [closed]

In the 2 minute BBC News audio clip Sesame Street: What is Count von Count's favourite number? "The Count" is asked Do you have a favorite number? to which he replied Thirty four thousand, nine ...
0
votes
1answer
20 views

prime factorization of rare and distinct rational numbers [closed]

The prime factorization of a natural number n can be written as n=pr ^2 where p and rare distinct and prime numbers. How many factors does n have, including 1 and itself?
5
votes
0answers
338 views
+200

Conjectured primality tests for specific classes of $k\cdot b^n \pm 1$

Can you provide proofs or counterexamples for the claims given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims: First claim Let $P_m(x)=2^{-m}\...