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

2
votes
1answer
76 views

Confused about the explicit formula for $\psi_0(x)$

In the explicit formula for $\psi_0(x)$ used in the PNT proof : $$\psi_0(x) = x - \sum_{\rho} \frac{x^{\rho}}{\rho} - \frac{\zeta'(0)}{\zeta(0)} - \frac{1}{2} \log (1-x^{-2}) $$ In particular the ...
3
votes
0answers
114 views

Are [Wieferich] primes the only solutions to $2^{n-1} \equiv 1 \pmod{n^2}$?

While studying a certain Diophantine equation in the integer $k \ge 2$, I believe I have proven the necessary restriction $$2^{k-1} \equiv 1\!\!\pmod{k^2}. \qquad(\star)$$ Based on what I read ...
2
votes
1answer
92 views

A problem about the discrete logarithm

suppose there are a multiplicative cyclic group $F_p^*(p \;is\;big\; prime)$, and $G=\langle g \rangle(g \;is\; a\; generator)$ is a subgroup of it and $G$'s order is $q(q\;is\;big\;prime \;and ...
1
vote
0answers
135 views

Value of sum with primes

Can anyone tell me the value of sum $\sum_p\left(\log p(\frac{1}{2p}-\psi(\frac{p+2}{2})+\psi(\frac{p+1}{2})\right)-\sum_n\frac{(\log(2^n)}{2^n}$ where $p$ ranges over prime powers and $n$ ranges from ...
4
votes
1answer
121 views

Fictional math proof = prime return function

I am trying to write a piece of future fiction where one of the characters is famous for proving an important truth related to primes. I want to make it as realistic as possible, but i'm not a math ...
2
votes
1answer
36 views

Need help to prove that $n \geq 3 \implies q_n = p_{n+1}$

Consider $q_n$ such that $$q_n = \sum_{k=2}^{2^n} k \left \lfloor \frac{1}{1 + \text{Abs} \left (n-\left \lfloor \frac{1}{a(k)} \right \rfloor b (k) \right )} \right \rfloor$$ where $$a(x) = ...
6
votes
1answer
116 views

Find all $n\in\mathbb{Z}^+$ satisfying : $n\mid(2^{\varphi(n)}+3^{\varphi(n)}+\cdots +n^{\varphi(n)}).$

Find all $n\in\mathbb{Z}^+$ satisfying : (i) $n$ has at most $4$ prime divisors . (ii) $n\mid(2^{\varphi(n)}+3^{\varphi(n)}+\cdots +n^{\varphi(n)}),$ where $\varphi(n)$ is the Euler function.
1
vote
1answer
71 views

What is the well-known result used to prove primality of $n=2pq+1$ under certain conditions?

On Henri Lifchitz's website, we find: If $n=2pq+1$, $p$ and $q$ primes and $q>2p$, if there is an integer $a$ such $a^{n-1} \equiv 1 \pmod n$ and $\gcd(a^{2p}-1,n)=1$ then $n$ is prime. It is ...
0
votes
1answer
81 views

Proving prime counting inequality

Let $n \in \mathbb{N}$ $$ 2n \ln 2 \leq \sum_{\{p \,\mid \, p \leq 2n+1, \,p\text{ is prime}\}} \ln(2n+1) = \pi(2n+1) \cdot \ln(2n+1)$$ Hint: Use $$\operatorname{lcm}(1, 2, \dots, 2n+1) \leq ...
0
votes
0answers
39 views

Primality Test with some condition

Given a prime number p, how can I quickly determine the primality of 10p+a, where a is an integer between 0 and 9? O(1) test is preferred Thanks!
6
votes
0answers
138 views

Coprime multiplicative orders modulo infinitely many primes

Is it true that there are infinitely many primes $p$ such that the multiplicative orders of $2$ and $3$ are coprime $\pmod{p}$? By this I mean their order in $(\mathbb{Z}/p\mathbb{Z})^*$. If the ...
4
votes
2answers
178 views

What is the most motivating way to introduce modular arithmetic?

What the best way to introduce congruences in a number theory course? I am looking for something which will have an impact. What are the really interesting applications of congruent mathematics?
2
votes
0answers
140 views

An upper bound on the least common multiple of the first $2n+1$ integers

Let $p$ be a prime number and let $a, n \in \mathbb{N}$. Then $$ p^a \mid \operatorname{lcm}(1, 2, \dots, 2n+1) \implies p^a \leq 2n + 1 \implies a \leq \dfrac{\ln(2n+1)}{\ln p}$$ and ...
5
votes
3answers
919 views

Is there a list of safe prime numbers?

I am looking for a list of precomputed safe prime numbers. Where can I get such a list?
0
votes
2answers
114 views

Nonexistence of Limit of Sum of Prime Factors

In trying to prove the following problem, I find great difficulty in proceeding to generalizing some results: Let $s(n)$ be the sum of prime factors of an integer $n$. Prove that $\lim_{n \to \infty} ...
4
votes
5answers
396 views

Is there at least one prime between $n \times 100$ and $(n \times 100) + 100$ where $n \in \mathbb{N}$

Is there at least one prime between the number $n \times 100$ and $(n \times 100) + 100$ for any $n \in \mathbb{N}$ that can be $0$ ? Question originally formulated by one of my friends.
2
votes
1answer
139 views

Using Mathematical Induction for a proof

How can I use Mathematical Induction to prove that there are an infinite number of prime numbers?
1
vote
2answers
109 views

Does $f(n)\sim g(n)$ imply $\lim_{k\to\infty} \frac{1}{k} \sum_n f(n)/g(n) = 1$?

Is it true that $$\lim_{k\to\infty}\frac{1}{k}\sum_{n=1}^k \frac{f(n)}{g(n)} = 1 \leftrightarrow f(n)\sim g(n).$$ My thought: $f(n)\sim g(n) \rightarrow \frac{1}{k}\sum \frac{f(n)}{g(n)} = 1$ since ...
3
votes
3answers
176 views

Cyclotomic Polynomial of a Prime

I have this question on a homework sheet: Claim:$$\Phi_{p}(x)=1+x+x^2+...+x^{p-1}\space$$ for $p$ prime. which was followed by the claim that $\Phi_{p^n}(x)=\Phi_p(x^{p^{n-1}})$ which I have ...
0
votes
1answer
49 views

Have either of these sequences been cataloged?

Let $x(n)$ be the remainder when $p(n + 2)$ is divided by 3, where $p(n)$ is the $n$-th prime. Let $y(n)$ = $x(n)$ - 1. Then $\{y(n)\}$ is a binary sequence, that is, is a sequence of $0$'s and ...
8
votes
2answers
149 views

How to prove $ \sum_{k=1}^{p-1}\left\lfloor \frac{k^3}{p}\right\rfloor=\frac{(p-2)(p-1)(p+1)}4 $?

Equation $(36)$ at Mathworld's Prim Sums page reads: $$ \sum_{k=1}^{p-1}\left\lfloor \frac{k^3}{p}\right\rfloor=\frac{(p-2)(p-1)(p+1)}4 $$ I'm curious how this can be proven, but I have no idea...
26
votes
1answer
2k views

A prime number pattern

The algorithm Given a natural number $n$ define a procedure as follows: Generate a list of primes upto and possibly including, $n$ Assign $Z = n$ If $Z > 0$, subtract the largest prime from list ...
7
votes
2answers
272 views

Compositeness of $n^4+4^n$ [duplicate]

My coach said that for all positive integers $n$, $n^4+4^n$ is never a prime number. So we memorized this for future use in math competition. But I don't understand why is it?
8
votes
4answers
781 views

Do there exist any odd prime powers that can be represented as $n^4+4^n$?

Well, I wrote up a solution on it, but according to the place I found the problem, it isn't quite correct. Ah, I'm simply hoping someone will point out where I got wrong. Now, let, $n^4+4^n = p^k$, ...
4
votes
2answers
98 views

Find prime numbers : $p_1,p_2,\cdots,p_8$ satisfying : $p_1^2+\cdots+p_7^2 =p_8^2$.

Find prime numbers : $p_1,p_2,\cdots,p_8$ satisfying : $p_1^2+\cdots+p_7^2=p_8^2$. Form test in class of my brother .
1
vote
1answer
37 views

Question on irreducible polynomials and primes.

Consider the polynomial $p(x) = 1+\sum_{i=1}^d a_i x^i$ where $a_i$ is binary and not all $a_i$ are $0$. Is it possible that $p(2^n)$ is prime for all integer $n>-1 ?$
2
votes
1answer
93 views

Unexpected data for primes?

I found some unexpected data for primes. Consider $p(n)$ being the product over all primes smaller than or equal to $n$. When factoring $p(n)^a +1$ for $a=1$ or $a=2$ we get the expected amount of ...
1
vote
1answer
1k views

Euler's Formula for Primes

Is there any way to prove that the Euler's Formula for Primes $n^2+n+41=41^2$ is valid? How would you even start to prove that a number is prime? If you could prove that a certain number is prime, it ...
3
votes
1answer
175 views

Calculation involving $\int_2^x \frac{dx}{\log x}$

Background (skip to the gray if you prefer). In Legendre's 1798 work on number theory he conjectured that $\pi(x)\sim \frac{x}{\log x - A}$ in which he proposed that $A = 1.08366.$ Gauss disputed the ...
1
vote
1answer
72 views

Squaring an integer quadratic

Let $Q(p)=37p^2-47p+4$. How does one go about finding all primes $p$ such that $Q(p)$ is a square of an integer? A bonus question. Is there a regular method to construct integer triples $(a,b,c)$ ...
1
vote
1answer
156 views

Ideals as a product of prime ideals

Suppose we are working in $\Bbb{Q}(\sqrt{-41})$. Given a ideal, for example $(2-\sqrt{-41})$ (we especially work in $\Bbb{Z}[\omega_{-41}]$). We know that this is a Dedekind ring, thus we have unique ...
4
votes
0answers
78 views

A bound for a certain set of prime numbers.

Let $p_n$ denote the $n^\text{th}$ prime. Find a lower bound for $\left|S\right|$ where $$S = \left\{ q \in \mathbb{N} \mid q \text{ is prime and } p_n - n \leq q \leq p_n + n \right\}. $$ Any good ...
2
votes
2answers
96 views

Assuming there exist infinite prime twins does $\prod_i (1+\frac{1}{p_i})$ diverge?

Assume there are an infinite amount of prime twins. Let $p_i$ be the smallest of the $i$ th prime twin. Does that imply that $\prod_i (1+\frac{1}{p_i})$ diverges ?
0
votes
3answers
226 views

Find 7 digit prime numbers with this property;

When you subtract the sum of the squares of the digits of the number from the original number it gives you another prime number squared.
1
vote
0answers
87 views

Conjectures about zeta functions and poles

Let $p^*_n$ be the $n$ th element of a subset of primes such that $p^*_{n+1}>p^*_n$ and $p^*_n < O((n+2) ln((n+2))^3)$. Define $f(z)$ as the analytic continuation of $\prod_{n>0} ...
2
votes
1answer
523 views

How can I find decompositions in $\mathbb{Z}[\sqrt{d}]$?

Decompositions in $\mathbb{Z}$ In $\mathbb{Z}$ you can find a decomposition of any element $n \in \mathbb{Z}$ by factorization such that $$n = \prod_{p \in \mathbb{P}} p^{v_p(n)}$$ So for a ...
1
vote
1answer
223 views

Pythagorean triples with additional parameters

I want to find solution in $\mathbb{Z}$ to the following quadratic Diophantene equation: $$na^2 + kb^2 = c^2$$ where $n,k,a,b,c \in \mathbb{Z}$, $n,k > 0$ and $(n,k) = 1$ I know that for some ...
2
votes
3answers
463 views

Prove that for every positive integer $n$ the number $(1−\sqrt 2)^n$ is not rational.

Prove that for every positive integer $n$ the number $(1−\sqrt 2)^n$ is not rational. Here is something I have, I'm not quite sure if I'm on the right track. Proof: Assume that $(1-\sqrt 2)^n \in ...
1
vote
1answer
321 views

Period of a decimal expansion

Show that if n is a product of m distinct primes, then the period of the decimal expansion of 1/n is the lowest common multiple of the periods of 1/p over all primes p|n. I understand that the above ...
7
votes
0answers
66 views

Infinite series with prime number [duplicate]

I know the $\sum_{n=1}^\infty \frac{1}{\text{Prime[$n$]}}$ does not converge, but what about the following series? $$\sum_{n=1}^\infty\frac{1}{\text{Prime[Prime[$n$]]}}$$ (Where $\text{Prime[$n$]}$ ...
4
votes
1answer
213 views

Is $k^2+k+1$ prime for infinitely many values of $k$?

Let's define an infinite sequence of positive integers as : $a_n=k^2+(2n-1)k+2n-1 $ , where $ k,n \in \mathbf{Z^{+}}$ Suppose that one can prove that this sequence contains infinitely many ...
15
votes
2answers
489 views

Is there a better upper bound for the primorial $x\#$ than $4^x$

In the classic proof of Bertrand's postulate by Paul Erdős, he shows that $x\# < 4^x$ where $x\#$ is the primorial for $x$. Is there any tighter upper bound for a given primorial $x\#$? Ideally, ...
1
vote
2answers
47 views

problem proving this property of congruence and primes

I've been working on this for a few days and I just can't seem to find a good proof for this. Given $a \equiv b\pmod{p_i}$, $i=1,2,3,\dots,n$ and $p_i$ is prime, show that $a \equiv b ...
1
vote
1answer
57 views

What's known about primes of the form $m^n+1$?

For example, the Fermat primes are primes of the form $2^{2^n}+1$. I'm wondering if the primes $m^n+1$ have a name. More importantly, I'm wondering if there are tables of these primes, and what else ...
0
votes
2answers
139 views

Primes dividing Integers

I randomly choose two integers. What is the probability that a certain prime number p does not divide both integers? Express your answer in terms of p.
14
votes
1answer
1k views

Would proof of Legendre's conjecture also prove Riemann's hypothesis?

Legendre's conjecture is that there exists a prime number between $n^2$ and $(n+1)^2$. This has been shown to be very likely using computers, but this is merely a heuristic. I have read that if this ...
1
vote
0answers
160 views

All Sufficiently Large Squares, Represented as Sum of Two Semiprimes

Define a semiprime to be the product of two (not necessarily distinct) primes, $p_iq_i$. Conjecture: All squares $\ge 4^2$ are representable as the sum of two distinct semiprimes. Case 1: Squares ...
2
votes
2answers
78 views

Stategy for prime factorization

How do I prime factorize big numbers, such as 8435674686325652 without having to make millions of divisions?
3
votes
1answer
348 views

Weaker Version of “Goldbach's Other Conjecture”

Taken from problem 46 on Project Euler: It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square. $9 = 7 + 2 \times 1^2$ ...
3
votes
3answers
3k views

Is the difference between consecutive prime numbers always an even number?

If we look at the difference between consecutive prime numbers, $p \gt 2$, it always appears to be an even number. For example, here are the seven consecutive primes starting at the $10^{10th}$ ...