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
111 views

The ultimate formula to factor them all.

Context I am working on Integer factorization problem, I found a formula for factoring numbers, and I need your help to simplify it. First I will explain how I get there and then I present the ...
-1
votes
2answers
83 views

Proof that if x is prime, then x+7 is composite. [closed]

Proof that if x is prime, then x+7 is composite. I do not know how to prove it. Can anyone help me to solve it? Thx
3
votes
2answers
69 views

When $\sqrt{(x+a)^2 -b}$ is an integer?

While working on integer factorization problem, I came to this: How to find for which values of $x$ the next equation is an integer? $$\sqrt{(x+a)^2 -b}$$ $a,b$ are positive known integers In ...
1
vote
1answer
19 views

Finding the rank of a particular number in a sequence of the sum of numbers and their highest prime factor

This question comes from a maths contest (infer no calculators or other electronic calculating aids) for 14-16 year olds (infer no use of complicated theorems, but those accessible to high-school ...
0
votes
0answers
51 views

The event: ($p$ is a prime and $p+2$ is also a prime) occurs *independentely* from the previous couples of twin primes: $(q,q+2)$ where $q<p$.

I am asking if there is a mathematical proof that the event: ($p$ is a prime and $p+2$ is also a prime) occurs independently from the previous couples of twin primes: $(q,q+2)$ where $q<p$, i.e., ...
2
votes
1answer
36 views

Prime elements in a noncommutative ring

Is there a reasonable definition of prime element in a noncommutative ring? The definition from wikipedia makes the assumption of commutativity and I'd like to know how necessary this condition is. ...
0
votes
1answer
27 views

Show number of integers $m$ with $1\leq m\leq n$, divisible by $p^h$ is equal to $\left[\frac{n}{p^h}\right]$

Let $n\in\mathbb{N}$, $p$ a prime number. Show that for each $h\in\mathbb{N}$, the number of integers $m$, with $1\leq m\leq n$, divisible by $p^h$ is equal to $\left[\frac{n}{p^h}\right]$, where ...
3
votes
2answers
132 views

Proving $\frac{p_{n+1}^2-p_{n+1}^{-C}}{p_{n+1}^2-1}>\frac{f(n) p_n \log p_n }{p_{n+1} \log p_{n+1}},$ where $f(n)\to1$, for some constant $C>1$

Are there two constants $C_1$, $C_2>1$ such that for large enough $n$ $$\frac{p_{n+1}^2-p_{n+1}^{-C_1}}{p_{n+1}^2-1}>\frac{2 C_2 p_{n+1} \log p_{n+1}-1}{2 C_2 p_{n} \log p_{n}-1} \left(\frac{p_n ...
-1
votes
1answer
37 views

Why 1 is not prime [duplicate]

I have been told that there is some interesting mathematics to why the number 1 is not prime. Can someone explain why one is not a prime number?
3
votes
1answer
68 views

Studying when $P_n=(p_1\cdot p_2\cdots p_n)+1$ is a square number [duplicate]

Let $p_n$ be the $n$th prime number. I need to find under which conditions the number $$P_n=(p_1\cdot p_2\cdots p_n)+1$$ is a square number. So far I have seen that $$P_1 = 2+1 =3$$ $$P_2 = 2\cdot3+1 ...
1
vote
3answers
37 views

Show that if $\gcd(x,y)=1$ then given integers $a,b$ there is an $m$ such that two congruences are satisfied

If $x, y$ are coprime, then for any integer $a,b$ there is an integer $m$ such that: $m \equiv a \;(\bmod\; x)$ $m \equiv b \;(\bmod\; y)$ I approached it like this: Since they are coprime then ...
2
votes
0answers
27 views

Is an upper bound known for the least exponent $k$ such that $(\pi(n^k)-\pi(n))_{n=1}^\infty$ is strictly increasing?

Is an upper bound known for the least exponent $k$ such that $(\pi(n^k)-\pi(n))_{n=1}^\infty$ is strictly increasing? It appears that the sequence is strictly increasing when $k\geq2$, but ...
0
votes
2answers
29 views

Demostrating that a number x is the smallest such that 24x mod (59) = 2 mod (59)

I have to find a number x such that x is the smallest natural number that satisfies this equation: $24x (\mod 59) = 2(\mod59)$. Using Fermat's little theorem and Euler's primes function, given that ...
1
vote
4answers
49 views

Show that $ar+bs=1$ implies that $a$ and $b$ are relatively prime

Let $a$ and $b$ be nonzero intergers. If there exist integers $r$ and $s$ such that $ar+bs=1$, show that $a$ and $b$ are relatively prime I don't really know how to show this, but here's an attempt; ...
1
vote
1answer
18 views

Use the euclidean algorithm to prove that if gcd(a,b) = 1 and a|c and b|c then ab|c

I am a bit confused here. I assume that: $gcd(a, b) = 1 \wedge c = ax_{1} \wedge c = bx_{2}$. I tried to find a formula starting from $a = bx_{3} + r$. But I didn't succeed, any tips?
4
votes
2answers
63 views

If $m,n$ are relatively prime, are there an infinitude of primes $mx^2 +n$

I know that Dirichlet's theorem says that there are an infinite number of primes of the form $mx+n$ I was wondering what we know when $x$ is squared. If for any reason we don't know if there are ...
1
vote
1answer
32 views

Closest rational approximation of $\sqrt x$ with denominator having prime powers $\lt n$

I am representing denominators in rational numbers with powers of their prime factors for easy multiplication and division in lowest terms (by adding and subtracting the prime powers). I would like ...
2
votes
1answer
38 views

Does every digit occur with equal frequency in the set of prime numbers?

Does every digit occur with equal frequency in the set of prime numbers? More precisely, let $f(n)$ be the total number of base-$b$ digits contained in the first $n$ prime numbers and let $f_d(n)$ be ...
-1
votes
2answers
40 views

An inequality using a prime counting function. [closed]

For how many positive integers $n < 1000$ is $\pi(n) > 2 (\phi(n))^{1/2}$ ?
2
votes
3answers
106 views

What is the largest known prime gap, and why is there so much conflicting information??

I find consistently conflicting information online. On the one hand there's all these reports of the largest prime gap between all numbers proven to be < 246. On the other hand, I read reports of ...
0
votes
1answer
32 views

Proof for whether or not a function will ever be non-prime.

From the proof that there are infinitely many primes: Given all the primes $p_i$ known up to the $n$th prime, construct the number $q_n$ such that $$ q_n = 1 + \prod^{n}_{i=1} p_i $$ Since there is ...
-1
votes
1answer
32 views

How to find the Number of factors, if sum of the factors are given?

A number is expressed in terms of $(2^m\times3^n)$, Find the value of $(m,n)$ if sum of all factors of a number is $124$.
2
votes
0answers
57 views

Reasoning about prime counting and the twin prime conjecture

I've been thinking the primorial for say the $i$th prime $p_i$and the equations for counting the number of elements in the reduced residue system for this primorial and counting the number of elements ...
0
votes
3answers
104 views

If $p$ divides $a^n$, how to prove/disprove that $p^n$ divides $a^n$? [duplicate]

The only thing I know for this problem is that an integer is a product of primes.
3
votes
0answers
70 views

Question regarding the prime factors of $2^{35} - 1$

Question regarding the prime factors of $2^{35} - 1$ I just wanted to make a few things clear; 1) It is true to state that this cannot be a Mersenne prime (A number of the form $2^r - 1$ where ...
1
vote
0answers
78 views

Is every integer $\geq5$ the sum of two primes and a power of a prime?

Is every integer $\geq5$ the sum of two primes and a power of a prime (where $1$ is included in the prime powers)? I don't really expect someone to prove this here, but I wonder if the question has ...
2
votes
1answer
85 views

Is there a sequence of real numbers so that $\sum_{n=1}^{\infty}x_n^p$ convergent iff $p$ prime?

Is there a real sequence $(x_n)$ such that the series $$\sum_{n=1}^{\infty}x_n^p$$ convergent if and only if $p$ is prime ? If the answer is YES, can we find an explicit formula for $x_n$ ? What ...
0
votes
1answer
20 views

Find one possible pair of values for x and y. If x,y and x-y are two-digit numbers. x is a square number, y is a cbe number and x-y is a prime number

Find one possible pair of values for x and y. If x,y and x-y are two-digit numbers. x is a square number, y is a cube number and x-y is a prime number. Is it as easy as I am thinking it is? Or I am ...
1
vote
1answer
29 views

Show $x_{r+1}$ defined as $x_{r}/2$ for $x_r$ even and $3x_{r}+1$ for $x_r$ odd goes to $1$ for all positive integer $x_0$. [duplicate]

Consider the following recurrence relation: $$x_{r+1} = \left\{\begin{matrix} x_{r}/2 &\text{if }x_r\text{ is even}\\3x_{r}+1&\text{if }x_r \text{ is odd}\end{matrix} \right. $$ I wrote ...
0
votes
1answer
52 views

Series of sinus for prime numbers

Is there a real number $\epsilon>0, \,\epsilon<\pi$ such that $$ \displaystyle \sum_{k=1}^\infty\operatorname{sin}(\epsilon\cdot p_k) $$ converges? Where $p_k$ is the kth primenumber.
4
votes
1answer
62 views

solutions of $p = 2q + r$

let $P$ denote the rational primes of the for $4k+3$, and let $Q$ denote the set containing $1$ and all the rational primes of form $4k+1$. let $p \in P$. we look for representations of $p$ of the ...
0
votes
0answers
13 views

Extending Newman's proof of PNT to bound the error term

Recently I've been getting into Newman's proof of PNT (explained nicely in this paper). Later I have been trying to find similar results which prove an error term in PNT, but all of them seem to ...
1
vote
1answer
34 views

Doubt on presumably divergent series with primes

I am wondering if my reasoning is correct. I want to determine if the following series converges or not: \begin{equation} \sum_{n=1}^\infty\frac{1}{(\ln p_n)^2} \end{equation} where $p_n$ is the ...
5
votes
2answers
62 views

Evaluate the sum $P=\sum_{n=1}^\infty \dfrac{a_n}{2^n}$.

Question: Let ${\{a_n}\}$ be the sequences of $0$s and $1$s, such that $a_n=1$ if $p$ is a prime number, otherwise $a_n=0$. So, ${\{a_n}\}={\{0,1,1,0,1,0,1,0,0,0,1,...}\}$. Evaluate the sum ...
5
votes
0answers
98 views

Is the Wikipedia article on the proof for Bertrand's Postulate correct?

I was checking out the Wikipedia article on the proof of Bertrand's Postulate. For Lemma 4, the argument is made for $x\ge 3, x\#<2^{2x-3}$ Here's the proof by induction: $n = 3$: $n\# = ...
2
votes
2answers
142 views

Integer factorization: What is the meaning of $d^2 - kc = e^2$

I found an interesting behavior when placing the integer factorization problem in to geometry, I call it pyramid factoring. Lets assume we have $c$ boxes and we want to order them in to rectangle. ...
2
votes
3answers
70 views

How to prove the following recursive sequence produce relatively prime numbers

Sequence an is defined recursively: $a_1 = 2$ $a_{n + 1} = {a_n}^2 - a_n + 1$ Prove that $a_i$ and $a_j$, $i \neq j$ are relatively prime. Hint: Prove that $a_{n + 1} = a_1 a_2 \ldots a_n + 1$ and ...
1
vote
2answers
105 views

For which prime numbers $p$ does the congruence $x^2 + x + 1 \equiv 0 \pmod{p}$ have solutions? [duplicate]

For which prime numbers p does the congruence $x^2 + x + 1 \equiv 0 \pmod{p}$ have solutions? We've recently learnt about quadratic reciprocity in class, however I am not sure how to tackle this ...
4
votes
1answer
52 views

Prime numbers making constant : 1.2527

Reading "Excursion in calculus" (Robert M. Young, 1992), exercice 13 on page 71 ask the reader to show there is a constant $c\approx 1.25$ such that $a_0=2^c$ $a_{n+1}=2^{a_n}$ $\forall n\; \lfloor ...
2
votes
1answer
37 views

$S=\{0,1,2,…,q^2-1\}$, is there a way to figure out how many elements contained in $S$ can be written as the sum of $2$ squares?

I'm currently working on a proof, and have broken it down into a series of problems. I've had success with every part except one. My question is (and it may be really easy; it's getting late): 'Let ...
1
vote
1answer
43 views

Is it easier to find $a^2-8c=b^2$ than $a^2-c=b^2$

I found a way to factor numbers if I find: $$a^2-8c=b^2$$ Where $c$ is the number I want to factor Is it easier than searching for the next equation? $$a^2-c=b^2$$
0
votes
1answer
47 views

If $2^{k} + 1$ is prime, prove that $k$ has no other prime divisors than $2$. [duplicate]

I am trying to prove this by contradiction: Assume $2^{k} + 1$ is prime. By definition of odd number $2^{k} + 1$ is odd because $2^{k} + 1 = 2\cdot 2^{k-1} + 1$ Then $2^{k} + 1 \pmod{2} \equiv 1 ...
2
votes
0answers
34 views

Does this approach for factorizing RSA numbers help in any way?

I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
0
votes
3answers
39 views

Proving if $p|ab$ then $p|a\vee p|b$, then $p$ is prime

Let $1\neq p\in \mathbb N$ such that $\forall a,b \in \mathbb N$ if $p|ab$ then $p|a\vee p|b$. Prove that $p$ is prime. My attempt, proof by contradiction: Suppose $p$ isn't prime, then ...
0
votes
1answer
19 views

Finding a module for the series $2^{i}$ from 0 to 219

How can I compute this: $\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$ I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq ...
1
vote
1answer
48 views

Integer factorization simplification

I found a small improvement to the brute force algorithm for the Integer Factorization. Please tell me if there is a point to investigate it more or there are better similar ideas. I found that if ...
1
vote
1answer
29 views

existence of solution to congruence $x^4 \equiv -4 \pmod p$

I stuck with the following question: For which $p$ (prime numbers) there is a solution for the following congruence: $x^4 \equiv -4 \pmod p$ I would greatly appreciate any help
2
votes
1answer
58 views

Existence of solution to Congruence relation $(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$

I'm taking the final exam in "Number Theory" tomorrow and stuck with: Prove that $\,\,\forall p\in\mathbb{Z}_p\,$ the congruence relation: $$(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$$ has a ...
17
votes
1answer
353 views

Short intervals with all numbers having the same number of prime factors

How to prove that for some $k, n_0$, for all $n \ge n_0$ it is never the case that all integers in $\{n, n+1, \dots, n + \lfloor (\log{n})^k \rfloor\}$ have exactly the same number of prime factors ...
1
vote
2answers
55 views

Prove that $\sum_{p \in \mathcal P} \frac1{p\ln \ln p}$ is divergent

In this question I've asked to decide the convergency of the series $\sum_{p \in \mathcal P} \frac1{p\ln p}$. Now I ask you to show that the series $$\sum_{p \in \mathcal P} \frac1{p\ln \ln p}$$ ...