# 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.

10,137 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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) + ...
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 ...
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) = ...
90 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 ...
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 ...
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 ...
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 ...
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 ...
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$$
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 (...
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 ...
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$$ ...
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 ...
203 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$ ...
94 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$ ...
79 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 ...
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-...
152 views

32 views

88 views

### $\mathbb{Z}$ mod $p$ vs. $\mathbb{Z}_p$

What is the difference between working in $\mathbb{Z}$ mod $p$ and working $\mathbb{Z}_p$? I'm mainly interested in the terminology and nomenclature, I understand that the result would be the same. ...
80 views

### Probability a natural number of the form $m^2 - n^2$ can be exactly factored as the product of $2$ primes?

Question Let $P$ be the probability that two integers where $m>1$is a fixed positive integer and $n$ is a randomly chosen such than $m> n \geq 0$? What is the probability $m^2 -n^2$ is ...
73 views

### Is there a way to find an upper bound for $n^2+an+b$?

I was solving the Project Euler: Problem 27. Considering quadratics of the form $n^2 + an + b$, where $|a| \lt 1000$ and $|b| \le 1000$ Find the product of the coefficients, $a$ and $b$, for the ...
36 views

### Finding all no-congruent primitive roots $\pmod{29}$

Finding all no-congruent primitive roots $\pmod{29}$. I have found that $2$ is a primitve root $\pmod{29}$ Then I found that is it 12 no-congruent roots, since $\varphi(\varphi(29)) = 12$ Then I ...
50 views

### prove/disprove: for all odd $n \geq 3$ we have $\sum_{k=1}^{n-1} p_k(n-k) \not \equiv 0\mod n$

Assume $p_k$ is the $k$th prime. I really don't know where to start except the fact I know that the numbers modulo $n$ form a group with the addition operator. All I know about the primes is ...
61 views

Let $p_1,p_2,p_3,p_4$ be odd primes. Problem Can it be shown that For every $k>1$, there exist at least one pair of $p_1,p_2,p_3$ and $p_4$ such as $$4k=(p_1-1)(p_2-1)+(p_3-1)(p_4-1)$$ Example $8=... 0answers 48 views ### Can a number N be expressed as sum of different primes. And if so, can we say goldbach conjecture is just a special case of it? I was looking into Goldbach Conjecture proof. Is it proved that we can express any integer as a sum of different primes. And if yes, Goldbach conjecture says we can do that with even numbers and ... 1answer 108 views ### Primes of the form$x^2 + 9 y^2$and$x^2 + 12 y^2$I've been studying primes of the form$x^2 + n y^2$(where of course$x$,$y \in \mathbb{Z}$) and I noticed the following: $$p = x^2 + 9 y^2 \iff p \equiv 1 \,\, (\textrm{mod} \,\, 12) \iff p = u^2 + ... 3answers 21 views ### Question about Rational numbers and prime numbers Suppose r is a rational number; then we can express r as r = \dfrac pq, where p,q are integers and q>0, and also p and q are relatively prime. What does "relatively prime" mean? 3answers 50 views ### Primes separated by multiples of 4 Q. Is it the case that for every prime p, there is a larger prime q such that q = p + 4 n, n \ge 2 ? For example: 5 + 8 = 13, 13 + 16 = 29, 29 + 8 = 37, and so on. I came upon this ... 1answer 59 views ### Determining primes in quadratic field \mathbb{Q}(\sqrt m) Given an algebraic integer \alpha (not a unit) \in \mathbb{Q}(\sqrt m), how to determine that \alpha is a prime? I know that the necessary condition is: The norm of \alpha is \pm p, where ... 1answer 491 views ### \lim_\limits{x \to \infty} \frac1x \sum_\limits{n\leq x}\mu(n)=0 \iff Prime Number Theorem I'm reading Analytic Number theory from Tom. M. Apostol's Introduction to Analytic Number Theory. In the fourth Chapter of the book he proves the equivalence of Prime number theorem with the ... 1answer 142 views ### Find the number of prime numbers p such that 2p^{4} − 7p^{2} + 1 is a perfect square. Have been trying to find the number of prime numbers p such that 2p^{4} − 7p^{2} + 1 is a perfect square.$$ 2p^{4} − 7p^{2} + 1 = n^{2} \\ 2p^{4} - 7p^{2} = n^{2} - 1 $$How do I move ahead? 0answers 32 views ### Question related to the expression of prime, twin-prime, and Sophie Germain prime counting functions in terms of Mertens function This question assumes the following definitions. (1) \quad\pi(x)==\sum\limits_{p\le x}1\qquad\text{(prime counting function where p\in P is a prime}) (2) \quad\pi_2(x)==\sum\limits_{p_2\le x}1\... 1answer 63 views ### Isomorphic finite rings? [closed] Let p be a prime number, P and Q monic polynomial of degree k\geq 2, irreducible over \mathbb Z_p. Do we have$$\mathbb Z_{p^2}[x]/(P) \simeq \mathbb Z_{p^2}[x]/(Q)\ ?$$1answer 27 views ### Question related to Sophie Germain Primes Assuming$p_i$is a prime consider the sequence defined by$q_1=p_i$and$q_n=2\ q_{n-1}+1$for$n>1$. Let$d$be the greatest value$n$for which$q_1..q_n$are all Sophie Germain primes which I ... 0answers 28 views ### Proof by using Euclid's Elements book i hope all you are fine. I have a question from Euclid's Element's book IX-14. It says that "If a number is the least that is measured by prime numbers, then it is not measured by any other prime ... 0answers 29 views ### Prove that$A(x)=\pi(x)+O(\sqrt{x}\log\log x)$This is an exercise in Apostol's Introduction to Analytic Number Theory about the prime number theorem (Chapter 13 Exercise 2). The problem follows: Let$a(n)$be an arithmetical function and$A(x)=...
Assuming that $n$ is an odd natural number greater than $2$, let $B(n)$ denote a sequence of bits between the leftmost and rightmost non-zero bits of the base-$2$ representation of $n$. The ...