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

4
votes
3answers
593 views

Relationship between prime factorizations of $n$ and $n+1$?

Are there any theorems that give us any information about the prime factorization of some integer $n+1$, if we already know the factorization of $n$? Recalling Euclid's famous proof for the infinity ...
1
vote
4answers
162 views

Equation involving prime numbers

Given the equation: $$p^2+\phi=q$$ where $p$ and $q$ are prime numbers and $\phi$ a constant, it seems the equation doesn't have solutions for $\phi=1,2,3$, but it has solutions for $\phi=4$. Is it ...
8
votes
2answers
396 views

Are there any elegant methods to classify of the Gaussian primes?

Out of curiosity, are there any relatively quick classifications of all the Gaussian primes, the primes in $\mathbb{Z}[i]$? I found a classification here, but the process comes off as rather tedious. ...
1
vote
0answers
164 views

factoring very very big random “numbers”

This is a variation on the theme of a rather flawed question that I asked months ago. Imagine a doubly infinite sequence, i.e. each member has a successor and a predecessor. Grab one term of the ...
1
vote
3answers
322 views

How to prove $p$ divides $a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}$ when $p$ is prime, $a, b \in \mathbb{Z}$ and $a,b \lt p$?

If $p$ is a prime number and $a, b \in \mathbb{Z}$ such that $a,b \lt p$, then how could we prove that $p$ divides $\left(a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}\right)$?
1
vote
2answers
314 views

Approximating next prime number

Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this? Edit: what happens if we limit ...
3
votes
2answers
132 views

Why is the probability that a prime p is a factor of a number n equal to 1/p

I'm learning some number theory and I can't seem to understand why this is the case.
2
votes
0answers
82 views

asymtotic ratio of nonsquarefree repunits

Let $R_n:=\frac{10^n-1}{10-1}$ (called a repunit) and $\mu$ be the Moebius function. Also $[n]:=\{1,2,3,\cdots, n\}, A_n:=\{m \in [n]| \mu (R_m)=0\}.$ What is the value of $\lim \limits_{n ...
5
votes
2answers
337 views

Polynomials representing primes

Suppose over $\mathbb{Z}$ we are given an irreducible polynomial $p(x)$. Can we say that $p(x)$ at least represents a prime as $x$ runs through integers? Thanks in advance
1
vote
1answer
169 views

Two Representations of $\log \zeta$

I was looking for representations of $\log \zeta$ and found these two: $ \displaystyle \log\zeta(s)=\color{red}{s}\sum_{n>0} \frac{P(ns)}{n\color{red}{s}}$ from here [$\color{red}{s}$ inserted ...
4
votes
0answers
526 views

Obtain a contradiction

Motivation : The motivation is to show that the equation $x^{2b}.x^{2a} +(3-x^{2b}) x^{a} + (1-s^2)=0 $ has no solutions in integers for any values of $x,b,a,s$ ( choosen as per the constraints ...
13
votes
1answer
385 views

Prime spiral distribution into quadrants

Is it known that the primes on the Ulam prime spiral distribute themselves equally in sectors around the origin? To be specific, say the quadrants? (Each quadrant is closed on one axis and open on ...
8
votes
2answers
238 views

Generalized PNT in limit as numbers get large

If $\pi_k(n)$ is the cardinality of numbers with k prime factors (repetitions included) less than or equal n, the generalized Prime Number Theorem (GPNT) is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln ...
2
votes
1answer
573 views

Explain Carmichael's Function To A Novice

I understand that the Carmichael Function (I'm going to call C()) is essentially the smallest positive integer m, where $a^m$ is congruent $1 \pmod n$ for all co-primes less than n. 6 makes sense to ...
1
vote
0answers
63 views

How are prime numbers used to facilitate modern encryption? [duplicate]

Possible Duplicate: Why are very large prime numbers important in cryptography? I'm interested in how the algorithms for creating key pairs to be used in dual key encryption work. I have ...
2
votes
2answers
2k views

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents.

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents. How would you write a formal proof for this.
1
vote
1answer
806 views

Primality and repeated digits

I recently worked on problem 51 through project euler, I solved it essentially through brute-force but afterwards I viewed the forum and there were some more clever solutions. For those unfamiliar ...
3
votes
4answers
157 views

To prove an elementary statement

I have an elementary doubt, Sorry for disturbing you all. I have a statement of this sort. $$r^2-1=p^a(f(p))=(r+1)(r-1). \tag{1}$$ Where $r$ is an even number, and $p$ is an odd prime. $f(p)$ is a ...
0
votes
1answer
90 views

How to generate a list of primes using the fundamental theorem of arithmetic

I've been told it's possible to generate a list of primes using the fundamental theorem of arithmetic, will someone show me how?
5
votes
7answers
5k views

Prime number generator, how to make

Can anybody point me an algorithm to generate prime numbers, I know of a few ones (Mersenne, Euclides, etc.) but they fail to generate much primes... The objective is: given a first prime, ...
7
votes
1answer
211 views

Flirtatious Primes

Here's a possibly interesting prime puzzle. Call a prime $p$ flirtatious if the sum of its digits is also prime. Are there finitely many flirtatious primes, or infinitely many?
-1
votes
1answer
147 views

cardinality of possible prime decompositions, countably infinite bijection

Let $A = \{ p_{i},p_{i+1},\ldots,p_{n}\}$ be any finite set of prime numbers, where $i,n \in \mathbb{N}$. And $p_{i}\in A$, is the $i$th prime number i.e. $p_{2} = 3$. Let all possible finite sets ...
1
vote
1answer
262 views

Unique Decomposition of Primes in Sums Of Higher Powers than $2$

Primes of the form $p=4k+1\;$ have a unique decomposition as sum of squares $p=a^2+b^2$ with $0<a<b\;$, due to Thue's Lemma. What is known about sums of $n$ higher powers resulting in ...
4
votes
3answers
965 views

$p=4n+3$ never has a Decomposition into $2$ Squares, right?

Primes of the form $p=4k+1\;$ have a unique decomposition as sum of squares $p=a^2+b^2$ with $0<a<b\;$, due to Thue's Lemma. Is it correct to say that, primes of the form $p=4n+3$, never have ...
4
votes
1answer
183 views

infinitely many prime numbers with prescribed digits

My main question is the generalization, though one can answer the first one and it will get accepted. Are there infinitely many primes involving $3,7$ only? Generalization: For what sets of given ...
1
vote
3answers
188 views

Need a “Prime Square” type of number (For my significant other)

No this isn't for a silly math exercise, it's a relationship with a hottie I don't want to lose at stake: I like my TV volume to be on Perfect Squares, but she likes her volumes on Prime Numbers. ...
12
votes
1answer
583 views

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square. I tried brute-force method and tried to find some pattern. I got $p=3,7$ as solutions . Apart from these I have tried for ...
1
vote
1answer
2k views

How to find large prime factors without using computer?

What is the largest prime factor of the number 600851475143 ? This is the third problem of Project Euler. How to approach this mathematically (without computer programming) ?
2
votes
1answer
304 views

Why is $\pi$ the Limit of the Absolute Value of the Prime $\zeta$ Function?

Motivation: I was looking at the approximation of the truncated Prime $\zeta$ function $$ P_x(s)=\sum_{p\leq x}p^{-s}= \mathrm{li}(x^{1-s}) + O \left(\cdot \right) $$ (to be found here with or ...
3
votes
4answers
73 views

How do I prove exchangeable modularity?

How do I prove that, considering all numbers natural, and p and i relatively prime, $mp+n \not \equiv 0 \pmod i$ is the same as $m-x \not \equiv 0 \pmod i$ considering x a natural number and the ...
6
votes
2answers
249 views

Do there exist infinitely many primes $p$ such that $a^{p-1}\equiv 1$ $\text{mod } p^2$ for fixed a?

I noticed that Hardy and Wright in their "An Introduction to Theory of Numbers"(sixth edition) have asked the following: Is it ever true that $$2^{p-1}\equiv 1 \text{mod} p^2\dots (*) ?$$ They ...
3
votes
1answer
221 views

constructive proof of the infinititude of primes

There are infinitely many prime numbers. Euclides gave a constructive proof as follows. For any set of prime numbers $\{p_1,\ldots,p_n\}$, the prime factors of $p_1\cdot \ldots \cdot p_n +1$ do not ...
3
votes
2answers
161 views

A series with prime numbers and fractional parts

Considering $p_{n}$ the nth prime number, then compute the limit: $$\lim_{n\to\infty} \left\{ \dfrac{1}{p_{1}} + \frac{1}{p_{2}}+\cdots+\frac{1}{p_{n}} \right\} - \{\log{\log n } \}$$ where $\{ x ...
10
votes
3answers
2k views

How to find the solutions for the n-th root of unity in modular arithmetic?

$$\begin{align*} x^n\equiv1&\pmod p\quad(1)\\ x^n\equiv-1&\pmod p\quad(2)\end{align*}$$ Where $n\in\mathbb{N}$,$\quad p\in\text{Primes}$ and $x\in \{0,1,2\dots,p-1\}$. How we can find the ...
11
votes
3answers
767 views

Proving a statement regarding a Diophantine equation

FINAL EDIT : Prove that if $p^z|n^2-1$ $$p^{x-z}(p^{z}-1)=\dfrac{ n^2-1}{p^z}-3$$ doesn't hold for any chosen values of $p,x,n$ and $z$. Here $p>3$ is an odd prime , $x=2y+z, \ ...
4
votes
1answer
168 views

Primes of the form $\lfloor x^k\rfloor$

I'm looking for a result (embarrassingly enough, a somewhat famous result) which shows the infinitude in some sense I don't recall of primes of the form $$ \lfloor x^k\rfloor $$ for $k$ fixed and ...
0
votes
1answer
239 views

Prime number in a grid for an identity matrix??

I was reading this Transversal of Primes, and the solution shown for an 11x11 grid. Made me think of an identity matrix. First, have each $a_{ij}$ be either 1 for a prime number or 0 otherwise. ...
4
votes
2answers
479 views

Proving ${p-1 \choose k}\equiv (-1)^{k}\pmod{p}: p \in \mathbb{P}$ [duplicate]

Possible Duplicate: Prove $\binom{p-1}{k} \equiv (-1)^k\pmod p$ The question is as follows: Let $p$ be prime. Show that ${p \choose k}\bmod{p}=0$, for $0 \lt k \lt p,\space ...
4
votes
4answers
186 views

Another Congruence Proof

I've been asked to attempt a proof of the following congruence. It is found in a section of my textbook with Wilson's theorem and Fermat's Little theorem. I've pondered the problem for a while and ...
2
votes
2answers
810 views

Product of all prime numbers upto some prime $p$

Let $p$ be a prime number. Denote by $P$ the set of all primes which are not greater than $p$. Is there a well known estimation of the product of all prime numbers in $P$ (i.e. $\prod_{q\in P}q$)?
22
votes
1answer
692 views

Primes approximated by eigenvalues?

Consider the matrix starting: $$\displaystyle T = -\begin{bmatrix} +1&+1&+1&+1&+1&+1&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ ...
8
votes
1answer
231 views

Is every natural number a prefix of a prime number? [duplicate]

Possible Duplicate: Proof that there are infinitely many prime numbers starting with a given digit string Let n be the representation of a natural number in a non-unary base. Is it a prefix ...
3
votes
2answers
131 views

Primes of the form $n\pm k$

Given some arbitrary natural number $n$, can we always find a $k$ such that $n+k$ and $n-k$ are both prime? Has there been any work on finding an upper bound for $k$?
8
votes
1answer
612 views

Primes of the form $p=a^2-2b^2$.

I've stumbled upon this and I was wondering if anyone here could come up with a simple proof: Let $p$ be a prime such that $p\equiv 1 \bmod 8$, and let $a,b\geq 1$ such that $$p=a^2-2b^2.$$ ...
0
votes
1answer
1k views

Why proof by induction fails for Goldbach's conjecture?

Can anyone clarify why induction method fails for this conjecture?
5
votes
2answers
505 views

Find the remainder when $ 12!^{14!} +1 $ is divided by $13$

Find the remainder when $ 12!^{14!} +1 $ is divided by $13$ I faced this problem in one of my recent exam. It is reminiscent of Wilson's theorem. So, I was convinced that $12! \equiv -1 \pmod {13} $ ...
2
votes
1answer
172 views

A prime conjecture

Let $n_k$ for $k=1,2,...,i$ be a finite sequence of positive integers, with $i>1$ and $n_1=0$. If there is a prime p such that for every positive integer m, one or more integers in {${(m+n_k)|1\leq ...
2
votes
4answers
206 views

A good introduction to Prime Numbers

I'm looking for a good introduction to Primes Numbers, their properties, and some of the better known theorems concerning them. I would prefer references assume knowledge of undergraduate level real ...
12
votes
1answer
528 views

The Goldbach Conjecture and Hardy-Littlewood Asymptotic

A source I am reading refers to the Goldbach conjecture (that every even number is the sum of two primes), and then immediately follows with the "Hardy-Littlewood conjecture" that $\sum ...
3
votes
1answer
92 views

Exclusive prime factors

Let $S$ be an finite or infinite subset of the primes. Let $f(x)=1$ if $x$ has no factors in $S$. If not, $f(x)=0$. Is there a way to calculate the limit $\displaystyle\sum_{n=1}^{x} f(n)/x$, as $x$ ...