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

3
votes
1answer
81 views

Divisibility Rules Of Primes and Roots

Let $a_1...a_k$ be positive integers that are pairwise relatively prime. Assume that $\sqrt[m]{a_1...a_k}\in\mathbb{N}$ for some $m\in\mathbb{N}$. Show that $\sqrt[m]{a_i}\in\mathbb{N}$ for each $i$. ...
7
votes
1answer
222 views

Prime number sum

Let $p$ denote a prime, and let $\{x\}$ denote the fractional part of $x$. Suppose that the following statement is true for all non-integer real numbers $x$: $$\lim_{n\to\infty}\frac{\sum_{p\leq n}^\ ...
1
vote
2answers
480 views

Chinese Remainder Theorem result varies

Sorry if this question is lame. First post! I was going through this book Abstract Algebra Theory and Applications Thomas W. Judson Stephen F. Austin State University In the Chapter ...
1
vote
1answer
251 views

Complexity of Pollard's p-1 method

I'm working on the complexity of various integer factorization algorithms and am kind of stuck on the complexity of Pollard's p-1 method. (I'm using Prime Numbers - A Computational Perspective by ...
2
votes
1answer
238 views

Is the product of 2 unique prime number unique?

I am wondering if I take the product of 2 unique prime numbers, and will the product be unique ? any chance to have collision ? I mean will any other 2 unique prime numbers have the same product ? ...
5
votes
0answers
169 views

Fastest Primality test using $N-1$ Factorization?

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality? Updated I'm aware of Pocklington primility test which is not good for ...
1
vote
1answer
80 views

Proof of non-prime integers.

$a_1, a_2$ and $a_3$ are distinct positive integers, such that $a_1$ is a divisor of $a_2 + a_3 + a_2a_3$ $a_2$ is a divisor of $a_3 + a_1 + a_3a_1$ $a_3$ is a divisor of $a_1 + a_2 + a_1a_2.$ ...
4
votes
2answers
187 views

Is there a prime number less than the product of consecutive primes, but greater than the last consecutive prime?

Let $P(k)$ be the product of $k$ consecutive primes $p_1, p_2, \dots, p_k$. So, e.g. $P(4)$ is $2 \cdot 3 \cdot 5 \cdot 7 = 210$. Is anything known about whether $P(k) > p_{k+1}$ is always true ...
4
votes
4answers
2k views

How can we prove that among positive integers any number can have only one prime factorization?

I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
0
votes
2answers
132 views

$k$ hands in $n$'s hair

Moderator Message: this question is from an ongoing competition. Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands ...
0
votes
2answers
63 views

Factorizing sum of two powers.

Is it possible to factorize, I'm trying to prove it isn't prime. $x^4 + 15^x$ If for what values of x will the above be prime, also any general method of determining if a really large number is ...
5
votes
2answers
298 views

Prime Arithmetic Progression with one fixed Element

For each prime $p$, we can consider the set of arithmetic progression made of primes that include $p$: $A_p=\{\{a_i\}_{i=1}^k \mid \text{$\{a_i\}_{i=1}^k$ is an arithmetic progression, each $a_i$ is a ...
3
votes
0answers
133 views

Estimation on Primorial Influence

As you know, Primorial ($\#$) notion is defined as the product of first $n$ prime numbers. That is, $$ n\# = \prod_{i=1}^nP_i $$ An there is some effect named Primorial Influence (explained ...
2
votes
1answer
124 views

Re-writing a series, involving prime numbers

Consider the limit $$\lim_{n \rightarrow \infty} \sum_{k=0}^n \frac{\Lambda(4k+3)}{(4k+3)}-\frac{1}{2}\ln(4n+3)$$ Where $\Lambda(n)$ is the vonmangoldt function, that is equal to zero if n is not a ...
0
votes
2answers
57 views

Prime congruence help

How can I find the smallest prime power $p^k$ such that ${p^k} \equiv b\bmod a$ given fixed $k$, $b$, and $a$ where $2\leq k$ and $b \ne 0$, $gcd(a,b)=1$, or say that that no solution exists.
1
vote
1answer
86 views

Whether any even number can be written in the form of (n-1)A+B ( where A and B are primes)

Can any even number be written in the form of $(n-1)A+B$, where $A$ and $B$ are primes and $n$ is an even number? $$ C= (n-1)A+B $$ Here $C$ is a even number and $A$ and $B$ are prime and $n$ is any ...
4
votes
1answer
85 views

Generating a large prime, $p$, such that $2^{k}$ divides $p-1$ for some $k<p$

I want to generate a prime $p$ of a certain size $2^{k}$ divides $p-1$ for some $k < p$. Is there any trick that I can use to do that instead of a brute-force search?
3
votes
1answer
170 views

What is this shortcut to determine primality?

I'm watching this, he says that David Slowinski discovered the biggest prime in 1984: $2^{132,049}$-1 and that it took 1 week on a Cray supercomputer: using some shortcut and that the absence of this ...
53
votes
4answers
4k views

$x$, $y$, $x+y$ and $x-y$ are prime numbers. What is their sum?

Here is the question: The $x$, $y$, $x−y$ and $x+y$ are all positive prime integers. What is the sum of all the four integers? Well, I just put some values and I got the answer. $x=5$, $y=2$, ...
4
votes
2answers
178 views

What's the meaning of “relatively prime to $p$”?

I'm reading mathematical gems, Vol.1: He states the Fermat's little theorem: If $p$ is a prime number, then for every integer a, the number $a^p-a$ is divisible by $p$. And then there's an ...
26
votes
5answers
3k views

How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4?

It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian ...
7
votes
1answer
260 views

Convergence of alternating series based on prime numbers

I've been experimenting with some infinite series, and I've been looking at this one, $$\sum_{k=1}^\infty (-1)^{k+1} {1\over p_k}$$ where $p_k$ is the k-th prime. I've summed up the first 35 terms ...
3
votes
2answers
237 views

Problems with Euler $\phi$ function (2)

If $a$, $b$ are coprime, then $$a^{\phi(b)}+b^{\phi(a)}\equiv 1 \bmod (ab) \, .$$ If $\left(n=2\phi(n)\right)$, then $n$ is a power of $2$.
0
votes
2answers
212 views

Congruence and prime numbers

$P$ is prime number. Prove the only solution for congruence $$x^2 \equiv y^2\pmod{p} $$ are $$x \equiv\pm y\pmod{p} $$ and give an example that exist other solution if n is composite number.
2
votes
1answer
86 views

A certain product over primes

There is this product over primes I came across, and I was wondering what the value would be asymptotically as $n$ goes to infinity. Could someone please help me out? Thank you! $$ \prod_{\text{primes ...
3
votes
3answers
191 views

What is the meaning of Chebychev's result and why is PNT stronger?

I saw the proof by Chebychev that there are constants $c_1,c_2$: $$c_1 \frac{x}{\log(x)} < \pi(x) < c_2 \frac{x}{\log(x)}$$ and the Prime Number Theorem states $$\lim_{x \to \infty} ...
3
votes
1answer
131 views

Infinite sum of powers of the prime zeta function

denote by $\zeta_{p}(s)$ the Prime Zeta Function. Now, consider the infinite sum: $$D(s)=\sum_{n=0}^{\infty}\zeta_{p}(s)^{n}=\frac{1}{1-\zeta_{p}(s)}\;\;\;\left | \zeta_{p}(s)\right|<1$$ $D(s)$ ...
5
votes
1answer
621 views

Super Perfect numbers

A super-perfect number is a number with $\sigma(\sigma (n))=2n$. How can I prove that every even super perfect number is from the form $n=2^k$ when $2^{k+1}-1$ is prime. I tried every way please ...
1
vote
2answers
76 views

Suppose $p$, $q$ are distinct odd primes, $a\in\mathbb{Z}$, and $q|a^p-1$ but $q\nmid a-1$

From the assumptions above, I am trying to prove that $q=1+kp$ for some integer $k$ and that $k$ is even. My thoughts thus far: Since $a^p\equiv 1$ mod $q$, I know that by a corollary of Fermat's ...
1
vote
2answers
222 views

Minimum Possible Number

How to find the minimum possible number of length N ,which is simultaneously divisible by the single digit prime number like 2,3,5,7 ?like of length 5 minimum possible number is 10080.
1
vote
1answer
100 views

What is the probability of $p_n$ being the greatest prime factor of a random number?

What is the probability of $p_n$ being the greatest prime factor of a random number?
4
votes
3answers
408 views

Expected smallest prime factor

For a random integer $x$ chosen uniformly between 2 and $n$, what is the expected value of the smallest prime factor of $x$ as a function of $n$? What is the behavior of the function as $n$ tends to ...
3
votes
1answer
64 views

Prove that for $A_k$ and $A_{k+1}$ when $A_n=n^2+3$, their largest common prime factor $\leq 13$

I need to prove that for any two following numbers $A_i$ and $A_{i+1}$ from the sequence $A_n=n^2+3$, their largest common prime factor must be $\le13$. It feels like I need to use the fundamental ...
4
votes
2answers
688 views

Prove that an odd integer $n>1$ is prime if and only if it is not expressible as a sum of three or more consecutive integers.

Prove that an odd integer $n>1$ is prime if and only if it is not expressible as a sum of three or more consecutive integers. I can see how this works with various examples of the sum of three or ...
3
votes
2answers
209 views

Proving A Theorem Concerned With Prime Numbers

I am in the process of reading this brilliant little book Prove It: A Structured Approach--very brilliant, have I mention that already? Anyways, here is the theorem: For every positive integer ...
3
votes
2answers
178 views

$p$ an odd prime, $p \equiv 3 \pmod 8$. Show that $2^{(\frac{p-1}{2})}*(p-1)! \equiv 1 \pmod p$

$p$ an odd prime, $p \equiv 3 \pmod 8$. Show that $2^{\left(\frac{p-1}{2}\right)}\cdot(p-1)! \equiv 1 \pmod p$ From Wilson's thm: $(p-1)!= -1 \pmod p$. hence, need to show that ...
6
votes
2answers
783 views

Finding the 2,147,483,647th prime number

In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a ...
1
vote
0answers
77 views

Primes clasification

For all numbers $N > n$ ( $n$ is positive number), let $p$ be an odd prime $<$ $(2N)^{1/2}$ and $d = 2N-2p+1$, then there exist at least an odd number $d$ which does not contain any odd prime ...
1
vote
1answer
83 views

Quadratic reciprocity - Product of primes

Let $n := pq$ for $p,q$ odd primes. Denote $J_n^1 := \{a \in Z_n^* \mid J_n(a) = 1\}$ and $J_n^{-1} := \{a \in Z_n^* \mid J_n(a) = -1\}$. I want to show that $|J_n^1| = |J_n^{-1}|$ where $J_n(a)$ ...
0
votes
2answers
141 views

Twin primes and modulo

I am so exited to learn math from this site. I posted the question today and I got good replies from members today itself. I will try to answer other number Theory questions in near future. With same ...
2
votes
2answers
344 views

What prime powers differ by one

I thought this would be a hard problem but I found a link that seems to ask the answer to this question as a homework problem? Can somone help me out here, are there an infinite number of prime powers ...
0
votes
1answer
47 views

Is the Mean Value of $|P_k(it)|$ equal to $\sqrt{k}$?

Let $P_k$ be the truncated Prime $\zeta$ function, like $$ P_k(it)=\sum_{n=1}^k p_n^{it}, $$ with $p_n$ being the $n$th prime. Numerics seem to indicate that the mean value of $|P_k|$ taken over all ...
7
votes
2answers
1k views

It it possible to “compress” a list of large numbers using their prime factors?

On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory. I'm wondering if it's possible in theory to use less memory if I store only prime factors ...
3
votes
0answers
82 views

Prime clasfication by some constructive function

How to prove or justify the following: $$ f(g)= \frac1{1-g^2} \prod_{k=1}^{\infty} \left(\frac{\sin(\pi \frac gk)}{\pi \frac gk} \cdot \frac 1{1-\frac{g^2}{k^2}}\right), $$ The above statment can ...
10
votes
2answers
328 views

Where can I find the modern proof of the prime number theorem?

Terence Tao described a modern proof of the prime number theorem in a lecture in UCLA, which is stated in wiki(enter link description here). From wiki: In a lecture on prime numbers for a general ...
0
votes
1answer
166 views

Goldbach conjecture and primes

I need some clarification on (1) Is there any proof to say Mersenne primes $M_p$ are finite or infinite? if there, could you share here.. (2) If Goldbach is conjecture is true, how you can justify the ...
2
votes
3answers
181 views

Primitive roots and Prime Numbers

Question: "Show that if $p$ is prime and $\gcd(d,p-1) = 1$, then every positive integer less than p is congruent modulo $p$ to the $d$-th power of some other integer." I understand that this is ...
1
vote
1answer
83 views

How many numbers exists that are smaller than $p$ and prime with $p$?

I have a homework to hand in and they asked this question. I don't know if I'm supposed to count 1 as a prime to that number or not. In my case $p=3947$, so I count 3945 numbers fitting that criteria ...
2
votes
1answer
85 views

$x^y \bmod n$ seems to repeat itself after some steps (when iterating over $n$)

Given $1516^{2627} \bmod 13$ I tried several things to find the solution without a calculator, such as examining some powers like $1516^{1} \bmod 13$, $1516^{2} \text{mod} 13$, $1516^{3} \bmod 13$ and ...
0
votes
1answer
166 views

Quadratic reciprocity - legendre symbol $\neq$ jacobi symbol

I want to calculate wether $\exists x : x^2 \equiv 123 \mod 11\cdot 13$ or not. I do know that in terms of the legendre symbol follows that $\neg(\exists x: x^2 \equiv 123 \mod 11)$ and $\neg(\exists ...