# 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
Filter by
Sorted by
Tagged with
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 ...
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$
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)$ ...
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 ...
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 ...
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, ...
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 ...
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 ...
34 views

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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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/...
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 ...
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) + ...
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 ...
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 ...
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) = ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$$
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 (...
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 ...
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$$ ...
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 ...
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$ ...
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 ...
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?
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$ ...
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 ...
### $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-...