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
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\...
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
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&...
3
votes
1answer
164 views

Uniquely identify any finite subset of an infinite set

Let $U$ be an unbounded subset of $\mathbb{N}$. Let $D = \mathcal{P}_{<\omega}(U)$ (the set of all finite subsets of $U$). Let $f$ be an injection such that: $f: D \rightarrow \mathbb{N} $ ...
5
votes
2answers
100 views

Sum of products of $(1 - 1/p)$

Let $\pi(n)$ denote the number of primes not greater than $n$, and $p_k$ the $k$th prime, so that $p_{\pi(n)}$ denotes the largest prime not greater than $n$. I'm interested in the value of the ...
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^...
-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 ...
5
votes
6answers
220 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
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^...
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$...
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 ...
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 ...
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 ...
8
votes
4answers
172 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
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.
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&...
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}...
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 3m,3m+1,3m+...
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
225 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 ...
60
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
386 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?, ...
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 ...
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 ...
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 ...
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 ...
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 , ...
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
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,...
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
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$ ?
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
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 $(^...
6
votes
3answers
114 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. ...
2
votes
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 $\sqrt{p}$...
-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 ...
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
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
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
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 ...