Questions tagged [prime-numbers]

Prime numbers are natural numbers greater than 1 not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

Filter by
Sorted by
Tagged with
5
votes
1answer
61 views

To prove that there are infinitely many prime numbers using topology

Proof Let $\tau$ denote that collection of $S(a,b)$. We show $\tau$ is topology. $\varnothing \in \tau$ is automatic. Next, since $\mathbb{Z} = \bigcup \{ n \} $ and $\{ n \} = S(1,0)$, then it is in $...
-1
votes
1answer
33 views

Are two distinct prime factorizations relatively prime to each other? [closed]

Consider two integers $x$ and $y$ and their respective prime factorizations \begin{equation} x = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} \dots p_{n}^{\alpha_{n}} \end{equation} and \begin{equation} y = ...
2
votes
1answer
67 views

Understanding the step in the proof about additive energy

I'm reading a paper on arXiv on additive combinatorics, and I have trouble understanding a step in the proof on page 16. Suppose $\Gamma \subseteq F^\times_p $ is a multiplicative subgroup of integers ...
1
vote
1answer
74 views

Infinitude of prime in the arithmetic progression$4n+1$

Is to possible to prove the problem with elementary approach as used to prove the case $4n+3$. Most of the proof that proves Infinitude of primes of the form $4n+1$ uses the some theorem from ...
5
votes
0answers
135 views

Understanding a specific method for applying the Chinese Remainder Theorem and its implications with regard to the lower bound of a solution

Observation: Consider the Chinese Remainder Theorem applied to this problem of $n$ remainders where each $p_i$ is a prime: $$x \equiv r_1 \pmod {p_1}$$ $$x \equiv r_2 \pmod {p_2}$$ $$\dots$$ $$x \...
2
votes
1answer
126 views

L. Gegenbauer's proof of Infinitude of Primes

I was going through the paper 'Euclid’S theorem on the infinitude of primes: A historical survey of its proofs' by Romeo Mestrovic where he mentioned that L. Gegenbauer proved Infinitude of Primes by ...
-1
votes
1answer
28 views

Arithmetic Sequences on Prime numbers [closed]

It is known that $a_1, a_2,$...$, a_{50}$ is an arithmetic sequence with common difference $d$, and $a_i (i=1, 2, ..., 50)$ are primes. If $a_1>50$, prove that $d>600,000,000,000,000,000.$ ...
0
votes
1answer
53 views

A claim regarding Perott's proof of infinitude of primes

The following is a picture from 'History of the theory of numbers, volume l Divisibility and Primality' by L. E. Dickson. Dickson wrote J. perott's proof of 'Infinitude of primes'. The first line does ...
0
votes
0answers
31 views

Small $p$ with $1-4A$ a square in $\mathbb F_p$

Is it true / known / easy to prove that for any integer $A>0$, there is an odd prime $p\le \sqrt A+1000$ such that $1-4A$ is a square (quadratic residue or $0$) modulo $p$?
0
votes
2answers
71 views

Infinite primes history

I am little confused with who was the first to modify Euclid's argument of infinitude of primes from $p_{1}p_{2}...p_{r}+1$ to $p_{1}p_{2}...p_{r}-1$? Some writers say it was E.E. Kummer ,($1878$) (...
1
vote
2answers
66 views

Primes between n/3 and n/2

I am interested in a proof that for all $n \in \mathbb{N}$ (with just a few exceptions) there will always be a prime $p$ such that $\frac{n}{3} \lt p \le \frac{n}{2}$. Note that the exact boundaries ...
1
vote
1answer
87 views

Using ordered pairs and sequences to give a required condition for any counter-example to Legendre's Conjecture

I found it very challenging to write this question. I apologize for any ambiguity. This is an argument that I am working on related to Legendre's Conjecture. I appreciate any questions or any ...
1
vote
0answers
38 views

Proving that for $x \ge 17$, $\prod\limits_{p < x\text{, prime, & }p \nmid (x^2+x)}p > x^2 + x$

Let: $x$ be an integer $p_n$ be the $n$th prime $x\#$ be the primorial of $x$ $f(x) = x^2 + x$ $P(x) = \prod\limits_{p < x\text{, prime, & } p \nmid f(x)}p$ $m(p_n)$ be the minimum $P(i)$ ...
3
votes
1answer
45 views

Any relation between primorial numbers and oblong (n(n+1)) numbers?

Just noticed that some primorial numbers are oblong: $\prod\limits_{i=1}^{3}p_i = 5 \cdot 6$ $\prod\limits_{i=1}^{4}p_i = 14 \cdot 15$ $\prod\limits_{i=1}^{7}p_i = 714 \cdot 715$ Does anyone know ...
3
votes
0answers
71 views

Proving certain inequality related to Primes [closed]

I was reading the following paper. But I can't understand why the last line concerning $\frac{2}{\pi}$ is true. The proof is a work of Sylvester. I would be happy if someone helps me in understanding ...
0
votes
1answer
60 views

To prove that $p$ is a prime number

I'm reading a book about proofs and fundamentals on my own and, currently, I'm having trouble proving this result. Theorem: Let $p$ be a positive integer bigger than or equal to $2$ and such that, ...
5
votes
1answer
105 views

Understanding Sylvester' s $1871$ paper of primes in arithmetic progression of the forms $4n+3$ and $6n+5$

The following is the proof of infinitude of primes in arithmetic progression of the form $4n+3$ and $ 6n+5$ done by Sylvester in $1871$ in his paper "On the theorem that an arithmetical progression ...
4
votes
1answer
222 views

Primality test for specific class of $N=12k \cdot 5^n+1$

Can you prove or disprove the following claim: Let $P_m(x)=2^{-m}\cdot\left(\left(x-\sqrt{x^2-4}\right)^m+\left(x+\sqrt{x^2-4}\right)^m\right)$ . Let $N= 12k \cdot 5^{n} + 1 $ where $k$ is an odd ...
2
votes
1answer
45 views

Is this a well known property of modular arithmetic

Let: $p_1, p_2$ be primes $x > 0$ be an integer where $p_1 \nmid x$ and $p_2 \nmid x$ I am interested in understanding the conditions where: $x - p_1 \equiv 0 \pmod {p_2}$ $x - p_2 \equiv 0 \...
0
votes
1answer
81 views

Why is the twin prime conjecture not obviously true?

Given there are infinitely many primes, why does this not then immediately imply there are infinite number of primes of gap 2? Does the infinite nature not imply that there are indeed infinitely many ...
2
votes
1answer
44 views

(soft) Can an efficient closed-form expression for $P_n$ be found? [closed]

I just read several old threads on here with people asking about formulas for primes, and what the implications of having one would be. As everyone was quick to point out, we already have a bunch, in ...
10
votes
2answers
149 views

Does the Riemann hypothesis guarantee that integer factorization is difficult?

In an exchange of comments at Is there any mathematical conjecture that is successfully applied in the real world in spite of being yet unproven?, user R.J. Etienne claims that RH guarantees that ...
4
votes
0answers
58 views

Is there a way to determine which coefficient of $an^2 - 1$ yields the most prime numbers?

I was wondering - is there a way to determine which coefficient $a$ yields the most primes in this expression: $$a \cdot n^2 -1$$ where $n \in \mathbb{N}$ and it goes from $[\alpha , \beta] ~~ \alpha,...
1
vote
3answers
64 views

The cyclic subgroups of $p^2$ order non-cyclic group are normal

I’m having a hard time on proving that every cyclic subgroup of $p^2$ order group is a normal subgroup, where $p$ is a prime number. I’m not going to use the truth that $p^2$ order group are abelian, ...
0
votes
1answer
47 views

Number theory question involving primes [duplicate]

Prove that, if a, b are prime numbers $a > b$, each containing at least two digits, then $a^4 - b^4$ is divisible by $240$. Also prove that, $240$ is the gcd of all the numbers which arise in this ...
4
votes
2answers
107 views

All prime divisors of $\frac{x^m+1}{x+1}$ are of the form $2km+1$.

Let $m$ be an odd prime and $x$ be the product of all primes of the form $2km+1$. Then all prime divisors of $\frac{x^m+1}{x+1}$ are of the form $2km+1$. What I know is that $\frac{x^m+1}{x+1}$ is an ...
5
votes
1answer
58 views

Comparing counts of relatively prime integers within a finite set

I am working on an approach to Legendre's Conjecture that depends on the following result being true (where $p$ is any prime, $n$ is any integer where $p \nmid n$): $$c_p(p,x) \ge c_p(n,x)$$ I am ...
3
votes
0answers
30 views

Is “second form” of Fermat's little theorem “stronger” than the first one?

These are the forms I'm talking about: $a^{p}\equiv a\pmod p$ $a^{p-1}\equiv 1\pmod p$ I thought that the only difference was that (1) is true even when p does divide a (producing a trivial ...
0
votes
1answer
93 views

Difficulty in understanding the proof of infinitude of primes in a certain arithmetic progression [closed]

Let $m$ as a fixed odd prime. How to show there are infinitely many primes of the form $2km+1$ (for some positive integer $k$). Can someone please help? Any help would be appreciated. Thanks in ...
4
votes
2answers
101 views

Prove that for an integer $x \ge 7$, it follows that $x\# > x^2+x$

Is the following argument sufficient to show that for an integer $x \ge 7, x\# > x^2 + x$. Please let me know if I made a mistake or if there is a more straight forward way to make the same ...
4
votes
1answer
52 views

A sum involving fractional parts and prime numbers

In this paper a formula involving fractional parts, denoted by $\{\cdot\}$, is derived \begin{equation} \sum_{\;\;\;\;\;d\leq x \\ d \equiv b \mod a}\Big\{ \frac{x}{d}\Big\} = \frac{x}{a}(1-\gamma) + ...
0
votes
1answer
48 views

Can be this prime numbers' property useful?

Today I've got a formula, which shows a way to write the result of multiplication between two generic integer $a$ and $b$. $$a \cdot b=\sum_{i=0}^{\min[a,b]-1} k-2i$$ where $k=a+b-1$. Showing it is ...
0
votes
1answer
54 views

For any positive integer n, let d(n) denote the number of positive divisors of n; and let φ(n) denote the

For any positive integer n, let d(n) denote the number of positive divisors of n; and let φ(n) denote the number of elements from the set {1, 2, · · · , n} that are coprime to n. (For example, d(12) = ...
2
votes
1answer
88 views

Infinite Primes in Arithmetic progression $10n+9$

Can anyone provide How J. A. Serret proved infinitude of primes in the arithmetic progression $10n+9$? I know there are many general proofs available now. But I want this one. Any help would be ...
3
votes
1answer
81 views

Showing sum of reciprocals of primes less than $2^{100}$ is less than $8$

The question is: Let $P = {2, 3, 5, 7, 11,...}$ denote the set of all primes less than $2^{100}$. Show that $$\sum_{p\in P} \frac{1}{p} < 8$$ I've looked through some articles about prime ...
0
votes
2answers
60 views

Why any integer $n$ can only have one prime factor greater than $\sqrt{n}$?

I know the proof that for a composite number $n$, there is at least one prime factor less than or equal to $\sqrt{n}$ but I don't know how to prove this following statement: Any number $n$ can have ...
2
votes
5answers
76 views

Odd prime $p$ implies positive divisors of $2p$ are $1,2,p,$ and $2p$

$1,2,p,$ and $2p$ are indeed divisors of $2p$. I want to show these are the only positive divisors. Is there a more elegant or concise way to prove this besides the proof I have below? Suppose that ...
0
votes
0answers
25 views

Can any number of the form $2p$, for $p>3$ a prime, be written as the sum of two distinct primes? [duplicate]

I think Goldbach's conjecture is quite well-know at this point, but there is no problem restating it: any even integer greater than $2$ can be written as the sum of two prime numbers. But what about ...
0
votes
0answers
37 views

How to prove this using modular arithmetics? [duplicate]

We know that p, q - odd primes such that $$(q - 1) | (p - 1)$$ and a is an integer such that $$ (a, pq) = 1 $$ How do we prove that $$ a^{p-1} \equiv 1 \mod pq $$
0
votes
1answer
29 views

Finding discrete logarithm of composite numbers

I started to learn discete logarithm the definition says that:suppose that "p" is a prime number , "r" is a primitive root (modulo p) and "a" is an integer between "1 and p-1" inclusive.If r^e (...
1
vote
1answer
60 views

Prove that 2 is not a primitive root of any prime of the form $3\cdot 2^n+1$ for $p>13$

I am really struggling with this proof. This doesn't seem like it should be that hard. All I have been trying to do is find a $k<3.2^n$ such that $2^k\equiv 1($mod $ 3\cdot 2^n+1)$, but it turns ...
1
vote
1answer
72 views

When finding $N$ primes will the total sum of $N$ primes always be $< 2^N$?

The prime gaps grow logarithmically. Now, suppose I create a list of $N$ primes. For example $N = 10$ or $[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$ then $$\text{total~sum} = 129$$ $$2^N = 1024$$ ...
0
votes
1answer
54 views

How to solve $x^{17}\equiv 37$ in $\mathbb{Z}/101\mathbb{Z}$? [duplicate]

I need to solve the equation $x^{17}\equiv 37$ in $\mathbb{Z}/101\mathbb{Z}$. I've looked into these topics (the calculation of the primitive root is missing, n is not prime) but couldn't derive a ...
6
votes
0answers
202 views

Are these well known properties of binomial coefficients?

I apologize for the number of definitions. I did not know how to state these ideas any simpler. If anyone can help me simplify the definitions, I will be glad to shorten the details. Let: $x,n$ ...
2
votes
1answer
93 views

Proof of prime in $(p,p^2)$?

Let $p$ be any prime. Let $S$ be the range of natural numbers in $[1, p^2]$. Suppose that there are no primes in $(p,p^2)$, which means that all prime factors of every number in $S$ must be $p$ or ...
0
votes
1answer
30 views

If $m,n,p$ and $m',n',p'$ produce the same Pythagorean triple, does the following have to hold? $m=m'$, $n=n'$ and $p=p'$.

A Pythagorean triple is given by $(x,y,z)=(p(m^2-n^2),p(2mn),p(m^2+n^2))$. Is there a way to show that $m=m'$, $n=n'$ and $p=p'$ or that there's possibly a counterexample where this isn't the case?
1
vote
1answer
43 views

A question about the probability of being a prime?

If we chose a random number $a \leq N$, then, the probability for $a$ to be a prime is $\frac{1}{\log N}$. Now, if there are some primes that do not divide $a$, then what is the probability for $a$ ...
0
votes
1answer
77 views

What is this sum? (related to prime numbers)

I was toying around with some prime number related series (trying to generalize some results from a puzzle) and came across this one: $$\sum_{p \text{ prime}} \frac{1}{p^2+p}$$ Is there any ...
2
votes
2answers
56 views

$4p+1$ is perfect cube, sum of all possible $p$ values?

This is a problem from a math Olympiad. $p$ is a positive prime number such that $4p+1$ is a perfect cube. What is the sum of all possible values of $p$? I have done this by trial-error and brute-...
2
votes
1answer
146 views

$\sum_{n=1}^{p-1}{\frac{1}{n}} = \frac{A_p}{B_p}$ What is $A_p$ (mod $p^2$) where $\frac{A_p}{B_p}$ is a reduced form fraction?

From Silverman's A Friendly Introduction to Number Theory, exercise 12.3 (This is not homework). We start with a prime number $p$ and let $$\sum_{n=1}^{p-1}{\frac{1}{n}} = \frac{A_p}{B_p}$$ where $\...