The prime-numbers tag has no wiki summary.
1
vote
1answer
28 views
What are the generators for $\mathbb{Z}_p^*$ with p a safe prime?
lets consider $\mathbb{Z}_p^*$ with $p = 2 \cdot q + 1$ a safe prime ($p$ and $q$ have to be prime).
Then $\varphi\left(p\right) = 2 \cdot q$ is the order of $\mathbb{Z}_p^*$, and ...
2
votes
1answer
85 views
Is there a simple way to prove Bertrand's postulate from the prime number theorem?
Is there a simple way to prove Bertrand's postulate from the prime number theorem?
The prime number theorem immediately implies Bertrand's postulate for sufficiently large $n$, but it fails to ...
2
votes
1answer
49 views
$(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod {m(m+2)}$
The Wiki page on Twin Primes says
The pair $(m, m+2)$ is twin prime, iff $4((m-1)! + 1) \equiv -m \pmod
{m(m+2)}$.
This is obviously connected to Wilson's Theorem. Can anybody provide a proof ...
1
vote
1answer
56 views
use contradiction to prove that the square root of $p$ is irrational
On a practice exam, our teacher provides us with this question and this answer.
Let $p$ be a prime number. Use contradiction to prove that $\sqrt{p}$ is irrational.
ANSWER: BWOC assume ...
5
votes
0answers
57 views
Limit inferior of the quotient of two consecutive primes
I have recently read an article about the prime number theorem, in which Mathematicians Erdos and Selberg had claimed that proving $\lim \frac{p_n}{p_{n+1}}=1$, where $p_k$ is the $k$th prime, is a ...
0
votes
0answers
40 views
public key crypto
Okay, i have basic knowledge of public key crypto and factoring but:
assume i have LOTS of high value sites I want to attack, lets say banks. Each has a public key pq to crack
assume I gather all ...
2
votes
1answer
71 views
Factoring a number knowing its totient
We are given: $n=p^aq^b$ and $\phi(n)$, where $p,q$ are prime numbers. I have to calculate the $a,b,p,q$, possibly using computer for some calculations, but the method is supposed to be symbolically ...
2
votes
1answer
68 views
How to find the factors of numbers around 1e7?
I don't have a maths background but I'm solving problems on the awesome Project Euler .net in JavaScript as programming practice.
I don't want to link directly to the question or post it verbatim ...
1
vote
2answers
62 views
Minimum set of US coins to count each prime number less than 100
Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set ...
0
votes
2answers
103 views
Proving $2^{\varphi(n)}\ge n$
To show $n\in\mathbb{N}\setminus \{6\}\Rightarrow 2^{\varphi(n)}\ge n$
I can't follow the proof from
http://mathematicalspectacles.blogspot.de/2012/05/interesting-study-of-zsigmondy-primes.html
...
6
votes
1answer
109 views
Always a prime between $x$ and $x+cf(x)$
What is the asymptotically slowest growing function $f(x)$, such that there exists constants $a$ and $b$, such that for all $x>a$, there is always a prime between $x$ and $x+bf(x)$?
$f(x)=x$ ...
6
votes
2answers
77 views
Question regarding Von-Mangoldt function.
Let $\psi(x) := \sum_{n\leq x} \Lambda(n)$ where $\Lambda(n)$ is the Von-Mangoldt function.
I want to show that if $$ \lim_{x \rightarrow \infty} \frac{\psi(x)}{x} =1 $$ then also $$\lim_{x\rightarrow ...
2
votes
4answers
144 views
Does this polynomial evaluate to prime number whenever $x$ is a natural number?
I am trying to prove or disprove following statment:
$x^2-31x+257$ evaluates to a prime number whenever $x$ is a natural number.
First of all, I realized that we can't factorize this ...
-1
votes
0answers
60 views
Prove fingerprinting [migrated]
Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that
$$\text{prob}(a \equiv b \pmod{p}) \le c \ln(n)/(n^{c-1}).$$
Hint: As a ...
1
vote
1answer
56 views
Value $\Phi_n(1)$ of the cyclotomic polynomial at x=1 [closed]
Possible Duplicate:
Value of cyclotomic polynomial evaluated at 1
I have to show $\Phi_n(1)=1$ for $n\neq p^k$ with $p$ is prime.
(I already proved to easy part $\Phi_n(1)=p$ for $n=p^k$)
...
1
vote
2answers
83 views
Name for prime numbers with only prime digits?
I'm wondering, is there a name for a prime number where all digits are also prime?
Some examples: 37, 53, 3253, 5573, 23753.
I've been calling them 'double primes', but I doubt that's the correct ...
-2
votes
1answer
188 views
My idea about finding the largest prime number [closed]
I have an idea about finding the largest prime number that I'd like to share with you guys and hear your feedback.
The idea is to use many computers to find the largest possible prime number, by ...
3
votes
1answer
65 views
Check for prime
I know there are a lot of questions on this board about finding prime numbers, and I've gone through a bunch of them. I even came across this interesting site about primes: ...
0
votes
1answer
76 views
Euler's sieve and wheel factorization
http://burntjet.co.uk/maths/primes/sieves.php#eq_sieve_div
I have read that Sieve of Eratosthenes algorithm can be speeded up with wheel factorization. Can similar be done with Euler's sieve (while ...
2
votes
2answers
61 views
Constructing pseudoprimes to the base 3.
When $n$ is a pseudo prime to the base 2, $2^{n}-1$ is also a pseudo prime to the base 2. This implies there are infinitely many pseudoprimes to the base 2. Then, how can I construct pseudoprimes to ...
2
votes
1answer
81 views
Primitive roots and the Chinese remainder theorem
I'm going over some past papers and have been able to show that if $p$, $q$ are distinct odd primes and $\gcd (a, pq)=1$ then $a^{\operatorname{lcm}(p-1,q-1)} \equiv 1 \pmod {pq}$
the next part says ...
1
vote
0answers
93 views
is it possible to get the Riemann zeros
since we know that the number of Riemann zeros on the interval $ (0,E) $ is given by $ N(E) = \frac{1}{\pi}\operatorname{Arg}\xi(1/2+iE) $
is then possible to get the inverse function $ N(E)^{-1}$ ...
4
votes
1answer
39 views
Non-linear Recursion
I'm trying to prove (or disprove and improve if possible) that the sequence $a_{n+1}=\frac{a_n^2+1}{2}$, where $a_0$ is an odd number greater than 1 contains an infinite number of primes. However, I ...
5
votes
5answers
310 views
Why do we consider prime numbers important, and what are their applications other than number theory in pure math?
Why do we consider prime numbers important, and what are their applications other than number theory in pure math? I know that Number theory is devoted to studying prime numbers, but there must be ...
0
votes
1answer
49 views
euler fermat and primes
Given $n\in\mathbb{N}$ we can write for $n>1$ :
$n=p_1^{a_1}\cdots p_s^{a_s}$ with primes $p_i$. Define $k:=lcm(\varphi(p_1^{a_1}),\ldots,\varphi(p_s^{a_s}))$ ( lowest common multiple)
I have to ...
4
votes
1answer
61 views
Find $k$-tuples satisfies $j=n_2+2n_3+\cdots+(k-1)n_k$ if $n_1+\cdots+n_k=n$.
Let $n_i \in N$, $i=1,\ldots,k$ and such that $n_1+\cdots+n_k=n$.
Fix $j \in N$.
I would like to find all $k$-tuples (or algorithm how to find $k$-tuples) satisfies
$$
j=n_2+2n_3+\cdots+(k-1)n_k
$$
...
4
votes
1answer
97 views
Does this $\zeta(s)$ identity have a name?
I have generalized the product from this thread:
Let $s=2n+1$ for $n\ge1$,
$$\zeta (s)=\frac{\zeta (2 s)}{\zeta (2)} \prod _{n=1}^{\infty } \frac{\sum _{i=0}^{s-1}(-p_n){}^i}{(p_{n}-1)p_{n}^{s-2}}$$ ...
6
votes
3answers
218 views
Characterizations of primes
Let $\mathbb{P}$ be the primes set.
We know from Wilson's Theorem that
$$(p-1)!\equiv-1 \pmod p \iff p \in \mathbb{P}$$
What another formulas we have with an if and only if ($\iff$) statement to ...
0
votes
1answer
58 views
Is there a forumla for number of primes preceding a natural number?
I am guessing there is no known analytical function which gives such a formula. This question came to mind while attempting a rather basic proof.
I am trying to show that the number of primitive ...
2
votes
2answers
74 views
Prime factorization of numbers
What is the smallest $x$ such that $x$ and $x+1$ both have exactly 4 not necessarily distinct prime factors?
4
votes
4answers
97 views
Proof of equivalence?
How do I prove that if two numbers $a$ and $N$ are co-prime, then in the equation:
$$ax ≡ ay \pmod N$$
necessarily $x ≡ y \pmod N$
3
votes
3answers
81 views
Prime number in a polynomial expression
Will be glad for a little hint: let x and n be positive integer such that $1+x+x^2+\dots+x^{n-1}$ is a prime number then show that n is prime
1
vote
3answers
43 views
Express the power of a natural number with the power of the product of prime factors
Given a natural number say $n \in \mathbb{N}$ with a prime factorization $p_1^{m_1} \cdot p_2^{m_2} \dots p_k^{m_k}$. If you take product of the prime factors $p_1 \cdot p_2 \dots p_k$ then the ...
0
votes
0answers
30 views
Connes trace operator
Given Conne's trace functional $ \displaystyle \operatorname{Tr}(U)(h)= 2h(1)\log\Lambda+ \int_K \frac{h(u^{-1})}{|1-u|}d*u $
what is the operator 'U' could someone write it down , what is the ...
0
votes
0answers
26 views
Cramer's conjecture and Hausdorff dimension
Cramer's conjecture predicts that $\limsup\dfrac{p_{n+1}-p_n}{(\log p_n)^2}=1$. Let's consider the set $A$ of all positive real numbers $a$ such that $0<\limsup\dfrac{p_{n+1}-p_n}{(\log ...
1
vote
3answers
115 views
Are the first 1,000 prime numbers enough to build every Goldbach number up to 9 digits long?
I'm writing a basic computer program in which one of my requirements is to find the smallest pair of prime numbers that make up a Goldbach number (up to 9 digits long, non-inclusive).
The user ...
4
votes
1answer
101 views
Primitives roots of $p$ and $p^2$.
It is well known that for any primitive root $g$ of a prime $p$, either $g$ or $g + p$ is a primitive root of $p^2$
Do there exist any primes for which $g$ is a primitive root of $p^2$ for all ...
1
vote
1answer
98 views
Numbering primes within a range.
$$n\ln n + n\ln\ln n−n < p_n < n\ln n+n\ln\ln n \mbox{ for } n\geq 6$$
This is the range where the $n$-th prime must lie.
However sieving within this range generates a large number of primes. ...
4
votes
1answer
86 views
How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?
Is there an easy way to compute the following question:
How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?
The only thing that ...
1
vote
1answer
58 views
How to select the values X and Y in the Sieve Of Atkin Algorithm
I came to know Sieve of Atkin is the fastest algorithm to calculate prime numbers till the given integer. I am able to understand the sieve of Eratosthenes from wikipedia page but i am not able to ...
0
votes
2answers
52 views
What are the specifics and the possible outputs of Pollard's Rho algorithm?
I'm trying to implement a simple prime factorization program (for Project Euler), and want to be able to use Pollard's Rho algorithm. I read the Wikipedia, wolfram|alpha, and planet math explanations ...
0
votes
1answer
83 views
Contiguous prime numbers with MPI (Want more ideas for an efficient algorithm)
I am a programmer. I am working with Message Passing Interface (MPI) in C. I do a program that consist on finding the contiguous prime from 1 to 10,000,000.
I already do it! but I do it with trial ...
26
votes
4answers
852 views
Could G. H. Hardy make a product of two primes so big he couldn't find out which?
This question of course began as a slightly irreverent play on the riddle, "Can God make a stone so big He can't lift it?" Then I wondered about the answer.
Is it possible to exhibit a number that is ...
0
votes
1answer
94 views
finding the greatest perfect square dividing an integer
how can we find the greatest integer which is a perfect square and which divides an integer? I believe factorisation can be used here but am not sure how to get the result out of it for all prime, ...
5
votes
1answer
90 views
Finding a point on Archimedean Spiral by its path length
I've been curious about Archimedean Spirals and their relations to Sacks Spirals and prime numbers.
I would like to draw some visualizations of the points with a given distance from the center, ...
1
vote
1answer
49 views
Distribution of Subsets of Primes
Primes may be divided in to sets: $p=4n\pm1$. Gauss showed, that if $p=4n+1$, it may be written also as $p=a^2+b^2$. From LagrangesFour-SquareTheorem, we know
that $g(2)=4$, where 4 may be reduced ...
1
vote
1answer
44 views
Sequence of first differences strictly increasing?
If $ \pi (x) $ := number of primes $ \leq x $, the operation
$T(x_{n+1}) = x_{n+1} - \pi(x_{n+1}) = x_n$
gives a sequence whose elements are those for which repeated application of T gives the ...
2
votes
2answers
135 views
Statistical observations about primes
Are there statistical observations about prime numbers showing that primes are not random? For example obviously primes are $1$ or $-1$ mod $6$, but are these remainder distributed equally? What I ...
7
votes
1answer
281 views
Finding a primitive root of a prime number
How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?
Thanks
12
votes
1answer
221 views
Is the clustering of prime powers merely coincidental?
$2^3$ and $3^2$ are close together; $11^2$, $5^3$, and $2^7$ (121, 125, and 128) are close together; $3^5$, $2^8$, and maybe $17^2$ (243, 256, and 289) are close together. $7^3$ is close to $19^2$ ...
