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

1
vote
1answer
64 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 = ...
-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
39 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 ...
5
votes
6answers
216 views

What is $\limsup_{n\to\infty} \frac{p_{n+1}}{p_n}$?

Let $(p_n)_{n\in\mathbb N}$ be the strictly increasing sequence of all primes. I'm wondering what $$S:=\limsup_{n\to\infty} \frac{p_{n+1}}{p_n}$$ is. Is the result already known? By Bertrand's ...
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
41 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 & ...
0
votes
1answer
43 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 ...
3
votes
3answers
133 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 ...
0
votes
1answer
36 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 ...
3
votes
3answers
52 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
47 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 ...
8
votes
4answers
170 views

Computing the first $n$ values of the Liouville function in linear time

Is it possible to compute the first $n$ values of the Liouville function in linear time? Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out ...
-2
votes
1answer
24 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.
1
vote
1answer
75 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 ...
4
votes
0answers
62 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
39 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 ...
7
votes
6answers
2k views

prime divisor of $3n+2$ proof

I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof I tried saying by the division algorithm the prime factor is either the form ...
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$. ...
0
votes
1answer
24 views

lower bound for Chebyshev first function [closed]

Is there a method to provide the a lower bound for $$\vartheta(x)=\sum_{p\leq x}{\ln p},$$ where $p$ runs over the primes ? Also, does anyone know of citations for the famous Chebyshev first ...
4
votes
2answers
224 views

$h+k=p-1$, $p$ prime. Prove $h!k! + (-1)^h \equiv 0 \pmod{p}$?

Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$. I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$ My first thought is that by ...
58
votes
5answers
6k views

Are there an infinite number of prime numbers where removing any number of digits leaves a prime?

Suppose for the purpose of this question that number $1$ is a prime number. Consider the prime number $311$. If we remove one $1$ from the number we arrive at the number $31$ which is also prime. If ...
8
votes
3answers
2k views

Does the sum of reciprocals of primes converge?

Is this series known to converge, and if so, what does it converge to (if known)? Where $p_n$ is prime number $n$, and $p_1 = 2$, $$\sum\limits_{n=1}^\infty \frac{1}{p_n}$$
21
votes
1answer
342 views

Is there any prime number of the form $0^1+1^2+2^3+3^4+4^5+…+(n-2)^{n-1}+(n-1)^n$?

Let A(n)= $0^1+1^2+2^3+3^4$....+$(n-2)^{n-1}+(n-1)^n$. So: A($1$)= $0^1$ A($2$)= $0^1+1^2$ A($3$)= $0^1+1^2+2^3$ A($4$)= $0^1+1^2+2^3+3^4$ and so on.... Is there a prime number of such form?, ...
9
votes
2answers
123 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 ...
4
votes
2answers
72 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
41 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 ...
19
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 ...
1
vote
0answers
20 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 ...
0
votes
0answers
61 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 , ...
2
votes
1answer
75 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
0answers
56 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 ...
11
votes
3answers
3k views

Cardinality of the set of prime numbers

It was proved by Euclid that there are infinitely many primes. But what is the cardinality of the set of prime numbers ? Cantor showed that the sets $\mathbb{Q}$ and $\mathbb{Z}$ have the same ...
2
votes
1answer
54 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$ ?
5
votes
1answer
4k views

The square root of a prime number is irrational

If $p$ is a prime number, then $\sqrt{p}$ is irrational. I know that this question has been asked but I just want to make sure that my method is clear. My method is as follows: Let us assume ...
0
votes
1answer
36 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 ...
6
votes
3answers
111 views

Prime numbers of the form $2357111317…$

Let $m_{n}$ be the number we get from putting first $n$ primes together. $$m_{1}=2$$ $$m_{2}=23$$ $$m_{3}=235$$ $$m_{4}=2357$$ $$m_{5}=235711$$ $$m_{6}=23571113$$ $$m_{7}=2357111317$$ and so on. ...
1
vote
1answer
5k views

use contradiction to prove that the square root of $p$ is irrational

On a practice exam, our teacher provides us with this question and this answer. Let $p$ be a prime number. Use contradiction to prove that $\sqrt{p}$ is irrational. ANSWER: BWOC assume ...
-4
votes
2answers
70 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 ...
26
votes
9answers
7k views

Is there possibly a largest prime number?

Prime numbers are numbers with no factors other than one and itself. Factors of a number are always lower or equal to than a given number; so, the larger the number is, the larger the pool of ...
3
votes
1answer
29 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 ...
2
votes
1answer
82 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 - ...
2
votes
2answers
90 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
27
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
0answers
26 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 ...
1
vote
0answers
54 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
507 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 ...
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 ...
7
votes
0answers
73 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 ...
2
votes
1answer
34 views

If $p$ is an odd prime show that $2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$

If $p$ is an odd prime show that $$2^{p-1}(2^p-1) \equiv 1 + 9p(p - 1)/2\pmod {81}$$ This is an exercise from Elementary Number Theory, 2nd Edition by Underwood Dudley. I know that the expression ...