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
2answers
271 views

Deterministic random numbers generator using $p^n \mod q$

I figured that I can create a deterministic "random" numbers generator by utilizing a bit of "magic" that I picked up from some cryptography. However I seem to have missed a detail. Basically the ...
1
vote
1answer
285 views

Invertibility of prime ideals in a number ring lying over prime numbers

I have trouble understanding an argument in the proof of the Kummer-Dedekind theorem. I am referring to a proof given in Peter Stevenhagen's notes. http://websites.math.leidenuniv.nl/algebra/ant.pdf ...
1
vote
2answers
1k views

What is the largest prime less than 2^31?

I'm sorry for this kind of specific question, I'd love if you could link to resources (prime lists, etc) that can answer similar questions more generically.
4
votes
2answers
194 views

Bounds on prime number spacing

Suppose n is an integer. What kind of bounds do we know for how close the closest prime p > n will be? I'd especially appreciate an answer that pushes me in the right direction of proving a good ...
6
votes
2answers
300 views

A Question on RH relating to Prime Number theorem

Well, in a previous post regarding the explanation of Riemann Hypothesis Matt answered that: The prime number theorem states that the number of primes less than or equal to $x$ is approximately ...
23
votes
2answers
9k views

Why are very large prime numbers important in cryptography?

Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others. Secondly, a friend asked me recently why large primes are important for data security, and I was ...
0
votes
3answers
530 views

Find x such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$)

Suppose you have two distinct large primes $p$ and $q$. Explain how you can find an integer $x$ such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$).
3
votes
1answer
832 views

Sum of divisors and prime numbers, short proof

Let $p_i$ denote the $i^{th}$ prime number. Find the smallest positive integer $k$ such that the product $n = p_1 \cdot p_2 \cdots p_k$ satisfies $\sigma(n) > 3n$. Is there any positive integer $m ...
2
votes
2answers
245 views

Prime divisibility

I have the following assertion in my notes from last year that I'm trying hard to digest, but I think it isn't true: If $p$ is prime $\Leftrightarrow$ if $p | ab$ then either $p | a$ or $p | b$ or ...
3
votes
1answer
424 views

Prime Number theorem and the prime counting function

Could someone please help me understand this proof given in an article by William Miller its supposed to follow from the prime number theorem that given, $A(x)$ which is the sum of all primes less ...
7
votes
4answers
1k views

Alternate definition of prime number

I know the definition of prime number when dealing with integers, but I can't understand why the following definition also works: A prime is a quantity $p$ such that whenever $p$ is a factor of ...
1
vote
2answers
852 views

Why do primes other than 2 and 5 divide infinitely many repunits?

I first noticed this is true for the integers of the sequence $9, 99, 999, 9999,\dots$, since for some term $a_n=10^n-1$ in the sequence and $p$ a prime other than $2$ or $5$, we have $a_n\equiv 0 ...
6
votes
2answers
417 views

Bijection between twin primes and numbers $n$ such that $n^2-1$ has exactly four positive divisors

I'm working my way through Niven's Introduction to Number Theory, and the wording of the following problem is making me unsure of my answer: Show that there is a one-to-one correspondence between ...
5
votes
6answers
921 views

Is it possible to find the position of a prime number online?

2 is the first prime number. 3 is the second. If I give a prime number such as 1151024046313875220631 is there any software/website which can give the position of the prime number. I know there are ...
1
vote
2answers
314 views

Finding the Value of $\sum\limits_{n=1}^{p-1} [\sqrt{np} \ ]$

How does one find the value of the sum : $$\sum\limits_{n=1}^{p-1} [\sqrt{np} \ ]$$ where $p$ is a prime such that $p \equiv 1 (\text{mod} \ 4)$. If i remember correctly, i got this sometime back, ...
8
votes
1answer
443 views

Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $[a,b]$

Consider the closed interval $[0,1]$, there is $\frac{2}{3} \in [0,1]$ where $p=2$ and $q=3$. Similarly consider $[2,3]$, one can have $\frac{5}{2} \in [2,3]$ where $p=5$ and $q=2$. Does every ...
5
votes
1answer
1k views

On the binary decimal expansion of the reciprocal prime's

I have been thinking a little bit about the binary decimal expansion of reciprocal prime numbers; and I have a few questions. I found this neat table which lists the binary expansion of many ...
10
votes
2answers
556 views

Mapping natural numbers into prime-exponents space

Take any natural number $n$, and factor it as $n=2^{e_1} 3^{e_2} 5^{e_3} ... p^{e_i}$, where $i$ is the $i$-th prime. Now map $n$ to the point $n \mapsto (e_1,e_2,\ldots,e_i,0,\ldots)$, where $i$ is ...
1
vote
1answer
251 views

Proving that a Number is Relatively Prime in a sequence

Prove that a number in the sequence $2,3,4,...,n \ (n>2$, is relatively prime to all other numbers if and only if it is a prime that exceeds $\displaystyle\frac{n}{2}$. Does such a prime always exist? ...