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.
9,981
questions
0
votes
0answers
12 views
Reasoning about a counter example to Legendre's Conjecture using ordered pairs and sequences
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 ...
0
votes
1answer
17 views
Proof that for every prime and pair of polynomials in $(\mathbb Z/p)[x]$, $x^p - x$ is a divisor of the difference
Show that for every prime $p$ and pair of polynomials $R(x)$, $S(x)$ in $(\mathbb Z/p) [x]$:
$$R(y) = S(y), y = 0, 1, ..., p-1 \iff x^p - x| R-S$$
that is, $x^p - x$ is a divisor of $R-S$
1
vote
0answers
29 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)$ ...
2
votes
1answer
28 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
47 views
Proving certain inequality related to Primes
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
52 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, ...
4
votes
0answers
42 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 ...
1
vote
0answers
38 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
34 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
46 views
Show that a polynomial has no rational roots, but has roots $\bmod p$, for every $p$ prime. [closed]
Given a polynomial $$Q(x) = x^6 + x^4 - 4 x^2 -4$$ show that is does not have any rational roots, but it has roots in $Z[p]$ for every $p$ prime.
0
votes
1answer
56 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
43 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 ...
-2
votes
0answers
20 views
How can I show that it is not prime? [closed]
$$Z[\sqrt{-5}]$$ $$1+3\sqrt{-5}$$ How can I show that it is not prime?
8
votes
1answer
91 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 ...
0
votes
0answers
38 views
Conjecture: prime sum of two squares between every pair of consecutive squares
It appears that between every $n^2$ and $(n+1)^2$, for $n \geq 1$, there's at least one prime that is a Pythagorean prime and can be represented as the sum of two squares.
In fact, it turns out that ...
4
votes
0answers
49 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
52 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
46 views
Number theory question involving primes
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
83 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 ...
4
votes
1answer
43 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
29 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
85 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 ...
-1
votes
0answers
27 views
Can you derive this expression for Cosā 5? [closed]
The number of sides of the regular pentagon is known to be a Fermat prime for the case of n=1.
If ā 5=2Ļ/5 Rdn, Cos ā 5 is a root of the quadratic equation x2 + 1/2 x - 1/4 =0.
This equation can be ...
0
votes
0answers
26 views
Why are there $\mathcal{O}(\dfrac{n}{\log n})$ prime divisors of value $\Theta(n^c), c>4$ wich divide a number $\leq 2^n$? [closed]
I am trying to understand this very small proof in in this picture from "A Fully Dynamic Algorithm for Maintaining the Transitive Closure" (https://www.sciencedirect.com/science/article/pii/...
4
votes
2answers
97 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
45 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) + ...
-3
votes
0answers
53 views
Infinite primes in Arithmetic progression [closed]
Can someone please provide the following proofs:
$(1)$ Lebesgue's proof of infinitude of primes in the arithmetic progression $2^{n} k +1$ where $n,k$ are fixed.
$(2)$ Lebesgue's proof of ...
0
votes
1answer
42 views
Can be this prime numbers' property usefull?
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
41 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
73 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
78 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
58 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
73 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 ...
1
vote
2answers
107 views
Can you explain why the coordinates of this third point are rational numbers? [closed]
The curve $y^2 = x^3 + 8$, contains the points $( 1, -3)$ and $\left( \frac{-7}{4}, \frac{13}{8} \right)$. The line through these two points intersects the curve in exactly one other point. Can you ...
-1
votes
0answers
56 views
How to find the numbers of factor $2s$ in $2048!$
As stated in the title.
I tried the prime factorisation of
$2048\times 2047\times 2046 \times \cdots$, but observed no strict patterns in the $2^{(n)}$ (e.g. $2048=2^{11}$,$2047$ is not factorsible ...
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
28 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
58 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
61 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
52 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
198 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
88 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
0answers
67 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
55 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-...
1
vote
0answers
54 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? [duplicate]
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 $\...
0
votes
3answers
84 views
Euler's product formula in number theory
Is there intuitive proof of Euler's product formula in number theory (not searching for probabilistic proof) which is used to compute Euler's totient function?
0
votes
1answer
48 views
$\sum_{t=1}^x e^{-\frac{1}{t}} $ approximating $\log_e(\pi(e^x))\sim x$
Related to a previous question: Is $\ln(\pi(e^x)) \sim x?$
$\sum\limits_{t=1}^x e^{-\frac{1}{t}} $ approximates a modified prime counting function $\ln(\pi(e^x))\sim x$.
This is similar I guess to $\...
