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.

learn more… | top users | synonyms

0
votes
1answer
30 views

Solutions to set of equations involving prime numbers

Is there a collection of distinct positive integers $(k_1, k_2, k_3, p_1, p_2, p_3)$ such that: $p_1, p_2, p_3$ are odd primes, and $k_1, k_2, k_3$ are odd $(k_1 + 2) p_1 = k_2 p_2$ and $(k_2 + 2) ...
1
vote
0answers
57 views

$\pi\left(\left(n+m\right)^2\right) - \pi\left(n^2\right) \ge 2 \cdot m$

Conjecture For $n \ge 1 $ , $m \ge 1$ $\pi\left(\left(n+m\right)^2\right) - \pi\left(n^2\right) \ge 2 \cdot m$ where $\pi\left(n\right)$ is the prime counting function . Does this conjecture ...
2
votes
1answer
89 views

How far to nearest/next prime?

Is there is metric to know how far we are from the nearest prime number. For example if my number is 38, then we are 3 numbers away from 41? If such a metric doesn't exist, is there an upper bound ...
2
votes
2answers
111 views

Express a prime $p$ as $p=a^2-2b^2$

Suppose $2$ is a quadratic residue modulo $p$ for an odd prime $p$. That is, there is an element $u$ such that $u^2 \equiv 2 \pmod{p}$. From here, can we prove that there exist integers $a$ and $b$ ...
4
votes
0answers
72 views

Prime numbers and arithmetic progressions

Whether there exist a polynomial $f$ such that for every $n$ there exist prime numbers $p_1, \ldots, p_n$, and an integer $b$ such that every $p_i$ and $b$ are less than $f(n)$ and $p_1×\ldots×p_n×b + ...
1
vote
1answer
75 views

Do all primes occur in some sequence associated with the Collatz conjecture?

Let $f(n) = \begin{cases} n/2, & \text{if $n$ is even} \\ 3n+1, & \text{if $n$ is odd} \end{cases}$ For an arbitrary prime $p$ are there some start value $x_0$ such that $p = x_k$ for some ...
0
votes
0answers
28 views

$\mid-1+2-3+4-5+6-7+10-11+…+(p_{k}-1)-p_{k}\mid=k$? Where $p_{k}$ is the $k$-th prime.

I'm not sure if it's a Telescoping series but I tried the generating rule to prove and test the series but I'm not getting any insight and I got stuck. Here are few Examples: $$\mid-1+2-3+4-5+6-7\...
7
votes
2answers
691 views

Proof of the following property about prime numbers

Is there a proper proof of the following property: Let $p$ be a prime number. The number of invertible elements in $\mathbb{Z}/p^n\mathbb{Z}$ is $(p-1)p^{n-1}$.
2
votes
0answers
49 views

Showing the infinitude of primes using the natural logarithm

I came across this proof in Proofs From the Book by Aigner and Ziegler. It uses the inequality $logx \leq \pi(x)+1$. (Here, we use natural logarithm) The proof starts with the inequality $log$ $x \...
4
votes
4answers
88 views

If $p > 3$ is prime, then $12 $ divides $p^2 - 1$

First up, I know there are a lot of similar questions with 24, not 12. So bare with me please :) What is the Question? Consider the following numbers of the form $p^2 - 1$ where $p$ is prime. $$5^2 ...
1
vote
1answer
72 views

Can composite numbers be uniquely written as a sum of two squares?

Let $X = a^2 +b^2$ where all the terms are positive integers and $X$ is a composite number and $\gcd(a,b)=1$ . Do there exist positive integers $c$ and $d$ other than $a$ and $b$ such that $X = c^2+d^...
11
votes
2answers
1k views

Twin prime conjecture proof error

I am absolutely sure this is wrong but I can't find why. For every integer $n$ there exist a finite number of primes less than $n$. Take the set containing those primes and multiply them together to ...
1
vote
1answer
31 views

Polynomial problem involving divisibility, prime numbers, monotony

Let $f$ be a polynomial function, with integer coefficients, strictly increasing on $\Bbb N$ such that $f(0)=1$. Show that it doesn't exist any arithmetic progression of natural numbers with ratio $r&...
-1
votes
1answer
32 views

Show that a positive integer $a>1$ is a perfect square (i.e., the square of an integer)…

if and only is in the prime decomposition of $a$ all the exponent are even integers. I don't understand what the question is asking. If I'm interpreting this correctly....any $a>1$ such as 9 would ...
1
vote
1answer
54 views

Generating all prime powers $\leq N$

Some very good algorithms exist to generate all primes $p$ up to some bound $N$, like the sieve of Erastothenes and the sieve of Atkin. However, suppose I want to generate a (sorted) list of all prime ...
0
votes
0answers
19 views

Field of the form $\{a+bi|a,b\in \mathbb{F}_p\}$

Artin, Algebra, Chapter 3, Ex 1.11 Consider whether the set of symbols $\{a+bi|a,b\in\mathbb{F}_p\}$ forms a field, if the laws of composition are made to mimic addition and multiplication of complex ...
0
votes
0answers
45 views

Some inequalities with Mangoldt function

Let $\Lambda$ be the Mangoldt function defined by $$-\dfrac{\zeta'(s)}{\zeta(s)}=\sum_{n=1}^{+\infty}\frac{\Lambda(n)}{n^s}$$ then $$\Lambda(n)=\left\{% \begin{array}{cc} \log p & \text{if}\;n=p^...
3
votes
3answers
143 views

If $p\nmid a$ (where $p$ is a prime), then prove that there is an integer $b$ such that $a\mid (p^b -1)$

If $p\nmid a$ (where $p$ is a prime), then prove that there is an integer $b$ such that $a\mid (p^b -1)$ . Though the thing seems easily verified through trivial put and check solutions, but I am ...
3
votes
0answers
54 views

The GCD of a Univariate Integer-Valued Polynomial over a Set

Let $\mathcal{I}[X]$ denote the subring of $\mathbb{Q}[X]$ consisting of all integer-valued polynomials (i.e., $f(X)\in \mathbb{Q}[X]$ such that $f(k)\in\mathbb{Z}$ for all $k\in\mathbb{Z}$). For $f(...
3
votes
3answers
54 views

How to demonstrate that $2^{2^n - 2} + 1$ is a nonprime number?

This, considering $n ≥ 3$. I have tried by induction; I suppose that it's true for all n less than or equal to k (and greater than or equal to 3), but then I stride when I go to prove for n = k + 1. ...
3
votes
1answer
53 views

Conjecture about odd primes

For each odd prime $p$ there exist $n\in\mathbb{N}$ such that $p\equiv n^2 \text{ (mod }\varphi(n^2))$, where $\varphi$ is Euler's totient function. I'm developing my Forth based computational ...
0
votes
1answer
38 views

Prime gaps and last digit of prime numbers

I recently saw a video about the last digit of prime numbers, that if a prime ends with a digit X then it is the least likely that the next prime also has X as the last digit. But I counted the prime ...
0
votes
1answer
44 views

Prove the integers in the arithmetic progression topology is not compact

I've been studying for my final exam in a general topology course, and I came upon this problem about compactness that I'm have a really tough time solving. Let $a$ and $b$ be integers, with $b\neq 0$...
-2
votes
1answer
29 views

Effective upper bound for a sum over prime numbers

Fix $y$ a positive real number. Is there an effective bound for the following sum i.e a positive constant B such that $$\sum_{p>y}\sum_{\nu \geq 4} \frac{1}{p^{9\nu/32}} \leq B.$$ Many thanks.
4
votes
0answers
70 views

Multiplicative group of $\mathbb{Z}/p\mathbb{Z}$ for a prime $p$ is cyclic

This question has been explored thoroughly, and in more generality too. For general fields, I am aware of standard proofs. However, I was naively trying to prove it in the simple case of prime $p$ ...
2
votes
1answer
40 views

Dividing primes

Let $p_1,\dots , p_{n+1}$ be distinct primes, let $\alpha_1, \dots , \alpha_n$ be integers, and let $a,b$ be integers. Suppose we had the equation: $$b^2p_{n+1} = a^2p_1^{\alpha_1}\dots p_n^{\alpha_n}...
1
vote
1answer
34 views

Prove amount of primes of form 4n-1 is infinite, looking for explanation of last part

This is an exercise in Bigg's Discrete Mathematics (Oxford Press). It is stated roughly like this: Suppose that there are finitely many primes of this form $(4n - 1): 3, 7, 11, 19,...,X$. ...
4
votes
2answers
74 views

Algebraic number fields in which all rational primes are inert

Is there an algebraic number field $F\supsetneq\mathbb{Q}$ such that all rational primes are inert in $\mathcal{O}_F$?
1
vote
0answers
46 views

The least prime factor of this super gigantic number (sequence)

I am planning to submit this sequence to oeis, and it is: $a(n)$ is the least prime divisor of $$2^{3^{5^{7^{11^{...^{p(n-1)^{p(n)}}}}}}}+p(n)^{p(n-1)^{...^{11^{7^{5^{3^{2}}}}}}}$$ Where the power ...
1
vote
0answers
22 views

How Euclidian Algorithm for division works with algebric expressions?

I am attending an introductory Number Theory class for Computer Science focused on cryptography. I have done some exercises with integers number but I have two exercises in which appears algebric ...
1
vote
1answer
76 views

Problem involving polynomial function and prime numbers

Let $f$ be a polynomial function, with integer coefficients, strictly increasing on $\Bbb N$ such that $f(0)=1$. Show that it doesn't exist any arithmetic progression of natural numbers with ratio $r&...
10
votes
2answers
131 views

Is a function of $\mathbb N$ known producing only prime numbers?

It is well known that a polynomial $$f(n)=a_0+a_1n+a_2n^2+\cdots+a_kn^k$$ is composite for some number $n$. What about the function $f(n)=a^n+b$ ? Do positive integers $a$ and $b$ exists such ...
0
votes
0answers
67 views

What are the prime factors of $4^{256}+253\ $?

I search a composite number near $4^{4^4}$ with a very large smallest prime factor. A candidate is $$4^{4^4}+253=4^{256}+253$$ The number is composite and has $155$ digits, so it is in the range , ...
3
votes
1answer
52 views

Roots of the equation $x^2+1=0$ in $\Bbb Z/p^{n}\Bbb Z$

Let $p$ be an odd prime number and $n$ be a positive integer. I want to consider roots of the equation $x^{2}+1=0$ in the ring $\Bbb Z/p^{n}\Bbb Z$. Suppose $n=1$. Find a condition on $p$ such ...
2
votes
1answer
55 views

Large Prime numbers

Say we have $2^{690} + 345^4$ and we want to figure out whether this is a prime number. I feel that we could break down the numbers into their respective prime factors (prime factorization) and use ...
3
votes
4answers
65 views

Fermat's little theorem question: why isn't $a^p \equiv 1$?

Fermat's little theorem says that $a^p \equiv a \pmod p$. I have kind of a stupid question. Since $p \equiv 0\pmod p $, why isn't $a^p \equiv a^0 \equiv 1 \pmod p$ ?
2
votes
1answer
77 views

Is there an equivalent to the Bertrand's postulate between factorials and primorials?

As the title explains, I am trying to know if there is a definition about the upper limit to find the first primorial $p_i\#$ (following the definition at OEIS) existing after a given factorial $n!$ (...
0
votes
1answer
37 views

Suppose that $ A^p = I_n $, show that $ (A-I_n)^p = 0 $

Let $A\in M_n({\Bbb F}_p )$. Suppose that $A^p = I_n$. Show that$(A-I_n)^p = 0$, and $A$ has an eigenvector $v\in {\Bbb F}^n_p$ with eigenvalue 1. I know that $p$ divides the binomial coefficient $(^...
-4
votes
2answers
79 views

Weird Prime Number Discovery [closed]

I noticed a strange phenomenon while examining prime numbers. Here it is: We'll say num = number If num's sum of digits is 4 and num is not even, num is prime. Can somebody explain to me why this ...
3
votes
1answer
30 views

If for $p \in \Bbb P$ and $x,y,z \in \Bbb N$ we have $x^{p-1}+y^{p-1}=z^{p-1}$, then $p\mid xyz$

I want to prove the statement in the title. This is, how far i came: Proof. We have $p \in \Bbb P$ and $x,y,z \in \Bbb N$ with $x^{p-1}+y^{p-1}=z^{p-1}$. If $p=2$, we have $x+y=z$. Now if $x$ and $y$...
2
votes
1answer
84 views

A number is prime if and only if …

Prove that a number $p$ is prime if and only if the $\gcd(\text{numerator},\text{denominator})$ of all fractions of the form $$\frac{1}{p - 1}, \frac{2}{p - 2}, \frac{3}{p - 3}, \ldots, \frac{k}{p - k}...
2
votes
2answers
94 views

Is $\frac{1010103010101}9$ prime or composite?

$1010103010101$ obviously divisible by $9$. Is $\frac{1010103010101}9$ prime or composite? The answer would be obtained without using WolframAlpha
0
votes
0answers
31 views

Relationship between Riemann Zeta function and Prime zeta function

In his paper, Daniel Grunberg shows a relationship between the Stirling Numbers of the first kind and the Harmonic numbers via series of partitions (see Equation 3.1 on Page 5 in the link above). If ...
28
votes
1answer
2k views

How can we turn any number into a prime number by simply adding more digits?

How can we turn any number (where the number is > 2) into a prime number by simply appending more digits? I'm referring to the right side of the number. So 4 is not a prime number But If I append ...
0
votes
2answers
21 views

divisibility of a product of (unique) primes by another product of (unique) primes

Assume that A is a set of prime numbers (without duplicates). Let P_A be the product of all elements of A. Assume that B is another set of prime numbers (again without duplicates) and let P_B be their ...
1
vote
0answers
61 views

Is this a new twin prime sieve method? Any information or comments is very appreciated.

I'm studying the twin prime numbers. Instead of sieving prime numbers, I found this method to sieve $\{x: x \neq \pm 1 \text{( mod $p$)}, x \in \mathbb{N}, p \le p_i\}$, so that $(x-1,x+1)$ will be ...
2
votes
2answers
513 views

What is the average prime numbers we've found till now?

When you count from 0 to 100 you have 25% prime numbers. Till now the largest prime consists of $2^{74,207,281}-1$ numbers. But is known what the average is till now? With average I just mean the ...
21
votes
3answers
2k views

How to prove that a very large number is not prime

I'm solving few math problems for an upcoming math contest . I am stuck with a short problem, where I have to prove that $A$ is not prime . $$A = 100\ 000\ 000\ 000\ 000\ 000\ 001$$ $A$ is not a ...
7
votes
0answers
81 views

Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
0
votes
0answers
60 views

Number of solutions to a modular equation of a specific form

I struggle with this Exercise, or at least the part where one should prove how many solutions there are. Simply inserting f=0 contradicts the suggested number of solutions. Let $p$ be an odd prime,...