Prime numbers are natural numbers 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

5
votes
3answers
336 views

Properties of Fermat primes

Fermat primes 17 and 257 appear a lot in the prime composition of numbers of the form $a^{2^n}+1$. For example, $11^8+1$ is divisible by 17 and $11^{32}+1$ is divisible by 257. I have verified the ...
10
votes
1answer
296 views

Primes of the form 1..1

For $n \ge 1$ an integer, let's denote $u_n = \sum_{k = 0}^{n-1} 10^k$ That is $u_1 = 1$, $u_2 = 11$, $u_3 = 111$, $u_4 = 1111$, ... My question is the following : Which of them are prime numbers ? ...
-2
votes
1answer
108 views

Primes classifications [closed]

1) If $p_1$$p_2$,...,$p_k$ be different primes and m = product of primes $p_1$,$p_2$,...,$p_k$ . How to prove that, when N = $N_1$ + $N_2$+...+$N_k$, where the prime factors of $N_i$ (here i is ...
3
votes
2answers
322 views

Primes and proofs

1) Are there infinitely many primes of the form $a_n$? if $p_1 = 2 < p_2 = 3 <\cdots$ is the sequence of primes then are there infinitely many $n$ for which $p_1p_2\dots p_n + 1$ is prime? For ...
3
votes
2answers
207 views

Split prime in $\mathbb{Z}[\sqrt{14}]$

I have this assertion: if $p$ is a prime such that $p\equiv 11 \pmod{56}$, then $p$ splits in $\mathbb{Z}[\sqrt{14}]$ (the discriminant of $\mathbb{Z}[\sqrt{14}]$ is $56$.) Why? Does $p\equiv ...
5
votes
1answer
96 views

Primes of the form $p_{i_1}p_{i_2}\cdots p_{i_n}+2k$

Let $S_{n,k}$ be the set of all numbers that can be written as the product of $n$ odd primes plus $2k$. Is there integers $n>1$ and $k>1$ such that $S_{n,k}$ contains finite number of primes?
12
votes
3answers
495 views

Twin primes of form $2^n+3$ and $2^n+5$

How to prove that $2^n+3$ and $2^n+5$ are both prime for only finitely many integers $n$? And how to prove that there are infinitely many primes of the form $2^n+3$ and $2^m+5$
1
vote
2answers
174 views

calculate $a^{(P-1)/2}\pmod{P}$ for large prime

How can I calculate $a^{(P-1)/2}\pmod{P}$? for example $3^{500001}\bmod{1000003}$ given that $1000003$ is prime. I know that if we square the number $3^{500001}$ the result will be either $1$ or ...
5
votes
1answer
532 views

Maximum order of integers coprime to a prime $p$

The following is a lemma I read online, but I don't understand part of the proof. Let $d$ be the maximum possible order among integers $a$ prime to $p$. Then for any integer $a$ not divisible by ...
4
votes
1answer
124 views

Prove that If $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci series where $f_1$=$f_2$=1

This problem came up in my conversation with a friend—not sure how basic it is, but it seems quite interesting: Prove that if $f_n$ where $n>3$ is prime, then $n$ is prime for a Fibonacci sequence ...
2
votes
1answer
528 views

If the order divides a prime P then the order is P (or 1)

I've just come up with this question as I'm studying for a number theory midterm. If $p$ and $q$ are different prime numbers, and it's known that $2^p \equiv 1 \bmod{q}$, then $q\equiv 1 \bmod{p}$. ...
4
votes
2answers
186 views

How to prove this inequality using prime number theorem

Define $s_n=p_{n+1}-p_n$, where $p_n$ is the $n$th prime number, now how to show that $$\lim_{n \rightarrow \infty} \inf \frac{s_n}{\log n} \leq 1$$ I used the result from the prime number theorem: ...
2
votes
2answers
74 views

Power equivalence in a prime modulus

Given, $p,q$ primes, $x$, $c$, $(p-1)/c$ integers and $$x^{(p-1)/c} \equiv 1\pmod{p}$$ how can I show there exists a $q$ such that $$q^c \equiv x\pmod{p}$$
4
votes
0answers
273 views

Prime zeta definition, multiplication by zero

Wikipedia has a page about the prime zeta function which is defined as follows: $$P(s)=\sum_{p\;\text{prime}} \frac1{p^s}$$ I entered this additional definition: Define a sequence: ...
9
votes
2answers
395 views

A limit involving prime numbers

Me and a friend of mine worked on building a problem for AMM. It all started pretty well, but in the end we realized that the initial part of the solution was wrong. In few words, we thought we have ...
-3
votes
1answer
93 views

primes proofs observations [closed]

1) Taking $p_1,p_2,\dots,p_k$ to be the primes up to $x^{1/2}$ we have a way to determine, with proof, each prime $N$ between $x^{1/2}$ and $x$ by Finding a representation of $N$ as in part c. Find ...
2
votes
1answer
95 views

For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$

I'm having a bit of difficulty writing a graceful proof for the following problem: For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$. Let $A$ be the ...
2
votes
1answer
103 views

With what probability is this polynomial equal to zero (mod a prime $p$)?

If we suppose that we have a polynomial $q(x)$ of the following form: $q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$ In other words, if we are given a polynomial with binary ...
4
votes
2answers
185 views

Is prime number defined to be some natural number or integer

In number theory, is prime number usually defined to be some natural number or some integer, i.e., must it be positive or can it be either positive or negative? Thanks and regards!
1
vote
2answers
424 views

The highest power of a prime that divides $f(x)$

I have read a result on computing the highest power of a prime that divides $n!$. I was wondering if there are any results on how to compute the highest power of a prime dividing $f(x)$, where $f$ is ...
1
vote
1answer
127 views

Prime asymptotics from Euler product

It is said that the Euler product $$\prod_p \frac{1}{1-p^{-s}}$$ diverges as $s \to 1^+$ proves we can't find constants $C$,$\theta$ with $\theta < 1$ such that $\pi(x) < C x^\theta$ because ...
1
vote
0answers
70 views

lower bounds for maximum computing times for integer factorisation

Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an ...
27
votes
3answers
535 views

Sequence of numbers with prime factorization $pq^2$

I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions: What is the ...
10
votes
5answers
250 views

Is there a single or best reason that 2 is an exceptional prime?

I've recently been studying some elementary number theory, and I've frequently come across the fact that there are a fair number of results (the main one being the law of quadratic reciprocity) for ...
3
votes
3answers
1k views

Riemann Hypothesis and prime number distribution

I do not grasp all concepts of the Riemann Hypothesis (better yet: as a layman I barely grasp anything...). However, I understand that there is a certain link between the Riemann Hypothesis and prime ...
2
votes
2answers
864 views

Congruence modulo prime power

In the book "A Classical Introduction to Modern Number Theory", I saw the following theorem (p. 43): If $p\neq 2$, and $p\nmid a$ then $p^{l-1}$ is the order of $(1+ap)$ mod $p^l.$ i.e. ...
2
votes
2answers
254 views

Set of prime numbers and subrings of the rationals

Let $P$ denote a set of prime numbers and let $R_{P}$ be the set of all rational numbers such that $p$ does not divides the denominator of elements of $R_{P}$ for every $p \in P$. If $R$ is a subring ...
5
votes
2answers
491 views

Prime factors of $n^2+1$

I know it is unknown if there are infinitely many primes of the form $n^2+1$. Is it known if there is a positive integer $k$ such that $|\{n\in\mathbb{Z}:n^2+1 \text{ has at most k prime ...
4
votes
1answer
189 views

A finite sum of prime reciprocals

How can you prove that $\sum\limits_k \frac1{p_k}$, where $p_k$ is the $k$-th prime, does not result in an integer?
4
votes
1answer
1k views

Prime-power decomposition of a square

I'm trying to learn number theory on my own, and here's a proof I'm not quite sure I got right. It feels too simple(?), I'm thinking maybe I'm missing something. So the question is: Prove that if ...
2
votes
2answers
273 views

How to show that $n$ is a prime?

Suppose that $n>1$ satisfies $(n-1)! \equiv -1 \pmod n$. Show that $n$ is a prime. (Hint: Antithesis) My own trying: $n=3$: $(3-1)!+1= 3 \cdot 1$ => $3|2!+1$. $n=5$: $(5-1)!+1=25 = 5 \cdot 5$ ...
5
votes
2answers
471 views

lower bound for the prime number function

Does there exist a function $f$ that is a lower bound of the prime number function $\pi$ with $f \sim \pi$?
1
vote
2answers
2k views

Help in understanding the proof of Mersenne Prime

Problem: $$\text{ If } 2^{n} - 1 \text{ is prime then n is prime}$$ Proof 1: $$\text{If } n = kl \text{ with } 2 \leq k, l < n \text{ then } (2^{k} - 1)|(2^{n} - 1). \text{ Hence if } 2^{n} - 1 ...
4
votes
3answers
247 views

Properties of the prime numbers?

Consider the following exercise: Let $P_1$ be the set of all primes, $\{2,3,5,7,\cdots\}$, and for each integer $n$, let $P_n$ be the set of all prime multiples of $n$, $\{2n,3n,5n,7n,\cdots\}$. ...
1
vote
1answer
909 views

Prime factorization of square numbers

Let n be a natural number with unique prime factorization $p^m$... $q^k$ . Show that n can be written as a square if and only if all (m, ...k) are even
1
vote
2answers
133 views

Moving powers in a prime modulus

Suppose I have $$x^{(c(p-1))} \equiv y^{(p-1)} \pmod{p}.$$ I would like to take the (p-1) root of both sides to get: $$x^c \equiv y \pmod{p}$$ I really just want to know if this a valid technique and ...
30
votes
2answers
632 views

Proof of no prime-representing polynomial in 2 variables

In "The New Book of Prime Number Records", Ribenboim reviews the known results on the degree and number of variables of prime-representing polynomials (those are polynomials such that the set of ...
3
votes
3answers
410 views

Prime satisfying a given condition

Let $p$ be a prime. If $\frac{p-1}{4}$ and $\frac{p+1}{2}$ are also primes then prove that $p=13$.
3
votes
1answer
286 views

Prime congruence

If $p\equiv3\pmod{4}$ and $q=2p+1$ is a prime then $q|(2^p-1)$ if $2^p-1$ is composite. Also, prove that there are infinitely many primes $p$ for which $2^p-1$ is composite.
1
vote
3answers
230 views

Number of factors of Carmichael numbers

Hello world! Now I'm implementing a stochastic (k-rounded) Fermat primality test for my annual scientific work. I know it is ...
1
vote
2answers
363 views

Ratio of primes

How can one find the limit as M approaches infinity of the ratio of the number of primes p to the number of primes q all less then M. Where every p satisfy: p+42 is prime, and p+20 is prime. And ...
3
votes
1answer
122 views

Formula for likely prime

Numbers of the form $n!+1$ are quite often prime numbers. Is there any formula $f(n)$ such that the probability that $f(n)$ is prime approaches 1 as $n$ goes to infinity and $f(n)$ also approaches ...
4
votes
3answers
117 views

Given $a$, $b$, and a prime $p$, how fast can we solve $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$?

If we're given two naturals, $a$ and $b$, and a prime $p$, how fast can we find two more naturals such that $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$? Additionally, you are allowed to precompute ...
3
votes
2answers
285 views

$n = 2^k + 1$ is a prime iff $3^{\frac{n-1}{2}} \equiv -1 \pmod n$

Let $k \geq 2$ be a positive integer and let $n=2^k+1$. How can I prove that $n$ is a prime number if and only if $$3^{\frac{n-1}{2}} \equiv -1 \pmod n.$$ Fixed.
5
votes
0answers
195 views

Sums of Dirichlet-Characters over prime numbers (part 2)

This is kind of related to my previous question that was poorly stated because of misreading my own notes that I have taken on the papers I am currently reading, so no surprise that it eventually ...
3
votes
3answers
506 views

How to check if an integer has a prime number in it?

Is there any way by which one can check if an integer has a prime number as a subsequence (may be non-contiguous)? We can check if they contain the digits 2,3,5 or 7 by going through the digits, ...
7
votes
1answer
193 views

Asymptotics of sums of Dirichlet-Characters over prime numbers

Again in relation with some stuff I am currently reading, the authors make use of the following "standard argument in prime number theory": Let $\chi$ be a non-principal Dirichlet-character. Then ...
1
vote
3answers
479 views

Can we use Peano's axioms to prove that integer = prime + integer?

Every integer greater than 2 can be expressed as sum of some prime number greater than 2 and some nonegative integer....$n=p+m$. Since 3=3+0; 4=3+1; 5=3+2 or 5=5+0...etc it is obvious that statement ...
11
votes
4answers
946 views

Proof that there are infinitely many prime numbers starting with a given digit string

To prove the following fact: given any sequence of digits in any base, eg 314159265358979323 base 10, there are infinitely many primes that start with these digits,eg when expressed in decimal they ...
2
votes
1answer
207 views

If a prime with prime norm is a split prime, in the number ring PID

If a prime with prime norm is a split prime , in an number ring PID? Example: $5-\sqrt{14}$ in $\mathbb{Z}[\sqrt{14}]$ has norm $11$, it is a split prime in $\mathbb{Z}[\sqrt{14}]$? Why? Thanks