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
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
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 ...
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
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$ ...
2
votes
1answer
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 ...
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
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 ...
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
152 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 $\...
0
votes
3answers
88 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?
1
vote
1answer
61 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 $\...
0
votes
0answers
32 views

How to find the congruence relation for the summation $\sum_{\substack{m<n_1<\cdots<n_r<p \\ n_i \equiv i \pmod 2}}\frac{1}{n_1\ldots n_r}$

Let $p$ be a prime number and $j\ge 0$. By changing the variables $n_i \mapsto p-n_i$, I know that $$\sum_{m<n_1<\cdots<n_r<p}\frac{1}{n_1\ldots n_r} \equiv (-1)^r \sum_{0<n_r< \...
0
votes
1answer
24 views

Number of positive integers less than $x$ that can be written as product of powers of finite primes

Let $p_1,p_2,...p_k$ be a finite set of prime numbers. Prove that the number of positive integers $n \leq x$ that can be written in the form $n=p_1^{r_1}p_2^{r_2}...p_k^{r_k}$ is at most $$ \prod_{i=1}...
1
vote
2answers
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. ...
0
votes
2answers
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
61 views

Show that, there exist pair of odd prime $p_1,p_2,p_3,p_4$ s.t. $4k=(p_1-1)(p_2-1)+(p_3-1)(p_4-1)$

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=...
0
votes
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 ...
4
votes
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 + ...
0
votes
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?
0
votes
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 ...
2
votes
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 $...
18
votes
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 ...
1
vote
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?
2
votes
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\...
-1
votes
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)\ ?$$
0
votes
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 ...
1
vote
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 ...
1
vote
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)=...
0
votes
0answers
47 views

Irrationality of the real number based on non-zero bits in the binary representations of primes

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 ...
2
votes
1answer
75 views

Prove that there are infinitely many odd number can't be written as $pq-p-q$

Let $p$ and $q$ are prime. Problem Are there infinitely many odd positive integer $a$, which can't be written as $pq-p-q$ ? Example $13$ can't be expressed in $pq-p-q$. Sequence $13,25,33,37,49,53,...
4
votes
1answer
53 views

is there any possibility to write and calculate this sum in pari gp, which is very related to hardy littlewood first conjecture?

I studied hardy littlewood first conjecture, which predicts the density of primes of special form, so: if I want to know the number of the primes of the form $2kp+1$, where $p$ is prime and $p \leq ...

1
3 4
5
6 7
203