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
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 $\...

1
2 3 4 5
200