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

4
votes
4answers
82 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
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 = ...
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
29 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 ...
-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
41 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
42 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 & ...
3
votes
3answers
134 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 ...
3
votes
0answers
49 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 ...
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
48 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
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 ...
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 ...
-2
votes
1answer
26 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
64 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 ...
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
73 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
43 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
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 ...
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 ...
9
votes
2answers
124 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
65 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
50 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
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$ ?
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
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 ...
-4
votes
2answers
73 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 ...
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
91 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
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 ...
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
56 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
508 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 ...
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 ...
7
votes
0answers
78 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
58 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 ...
2
votes
1answer
35 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 ...
-1
votes
0answers
44 views

Connection between prime numbers and transcendental numbers

I think there may be a strong connection between prime numbers and transcendental numbers. I am unable to prove what I have in mind by myself, so I am seeking help. My hypothetic theorem would be: ...
21
votes
1answer
352 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?, ...
-2
votes
0answers
32 views

Supposed p is a prime Number such that (p-1)/4 and (p+1)/2 are also primes. Show that p=13

$p$ is not $2$ or $3$ (otherwise $\frac{(p-1)}{4}$ would not be an integer).Hence p must be an odd prime. Also $p-1$ is divisible by $4$ $p = 4t + 1$ (say) $\frac{(p-1)}{4}=t$ $\frac{(p+1)}{2}=2t$ ...
3
votes
0answers
37 views

Why do we know that , besides the known idoneal numbers , there is at most one more?

Here https://en.wikipedia.org/wiki/Idoneal_number the definition of an idoneal number is given : A number $n$ is idoneal if there are no integers $a,b,c$ with $0<a<b<c$ and $n=ab+ac+bc$ A ...
1
vote
1answer
60 views

Let $P$ be a prime. Show that $\exists$ $x \in \mathbb{N}$ such that $f(x) = p$ then $\exists$ $y \in \mathbb{N}$ such that $g(y) = p$

What is given? $$\text{Let P be a prime}$$ $$\text{Let} \space f(x)= 3x+1$$ $$\text{Let} \space g(x)= 6x+1$$ Show that: If there exists $x \in \mathbb{N}$ such that $f(x) = P $ , then there exists a ...
5
votes
4answers
99 views

Should we or should we not take $1$ as a prime number? [duplicate]

I think I know that there were times in the past when it was convenient to look at a number $1$ as a prime number, and, as far as I can remember, even then it was dependent on who we ask is it prime ...
1
vote
1answer
28 views

The prime counting function has a lower bound of $C\log\log x$

I read that using Euclid's Theorem and by induction, a "gross underestimation" of the Prime Counting Function $\pi(x)$ can be stated as $C \log \log X$, i.e there is a constant $C$ such that the ...
2
votes
1answer
44 views

If $0 < a < b,$ there exists an $x_{0}$ such that for $x \geq x_0$ there is at least one prime between $ax$ and $bx.$

My approach: I first showed that for $0 < a < b,~\pi(ax) < \pi(bx)$ if $x \geq x_{0}.$ Now, since $\pi$ is an integer valued function, $\pi(bx) - \pi(ax) \geq 1$ for all $x \geq x_0.$ i.e. ...