Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

-1
votes
2answers
19 views

prime numbered currency

The unit of currency is the Tao(t) the value of each coin is a prime number of Taos. The coin with the smallest value is 2T there are coins of every prime number Value under 50. Help! I don't under ...
-2
votes
1answer
28 views

Show that $1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$

Let $p$ be an odd prime, and let $n$ be an integer not divisible by $p-1$. Show that $$1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$$
0
votes
1answer
54 views

Prove that for any prime p, there are integers x and y such that $p|(x^2+y^2+1)$

I asked this question a couple days ago, Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. but as I asked it as a guest, I could not comment on the ...
-1
votes
3answers
39 views

show that $3^{(p-1)/2} +1$ is divisible by $p$ [on hold]

let $n$ be an integer $>1$, and suppose that $p=2^n+1$ is a prime. Show that $3^{(p-1)/2} +1$ is divisible by $p$ (First show that $n$ must be even)
2
votes
1answer
43 views

$\displaystyle\prod_{ p\leq x}p\leq 4^{x-1}$ for all real $x\geq2$

How yo prove this? I'm looking the Erdös proof from Bertrand Postulate and there are many things I don't get. Please don't hints, I'm newbie in combinatorics techniques. In the book I don't get how ...
1
vote
1answer
21 views

Proving consecutive quadratic residue modulo p [duplicate]

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]
-1
votes
0answers
22 views

Quadratic residue dependency on $\bmod 4$ [duplicate]

Let $p$ be an odd prime and let $a$ be a quadratic residue modulo $p$. Write a formal proof showing that $−a$ is also a quadratic residue modulo $p$ if and only if $p ≡ 1 \bmod 4$. I sort of ...
0
votes
1answer
21 views

Dixon's factorization method Example

This Wikipedia article documents this algorithm: For example, if N = 84923, we notice (by starting at 292, the first number greater than √N and counting up) that $505^2$ mod 84923 is 256, the ...
0
votes
1answer
26 views

Find the set of primes p for which -3 is quadratic residue mod p

Find the set of primes $p$ for which $-3$ is quadratic residue $\text{mod } p$. I have started my solution like this: $1= \left(\dfrac{-3}{p}\right) = ...
0
votes
1answer
32 views

Is it possible to bound recurrence functions for primes?

Would it be possible to bound this function for primes in terms of the maximum difference between the images of the function and their closest primes (for instance, the fifth term is 33 and has ...
0
votes
1answer
38 views

Difference between generalized cuban primes and cuban primes.

I have been studying cuban primes and while the official definition of cuban primes contains only two variations, I have also seen a reference to generalized cuban primes, which has a much larger set. ...
1
vote
0answers
10 views

lattice walks with primes and composites

In the regular square lattice create a walk moving according the value of a counter. Consider two types of walks: In the first walk advance forward one unit if the counter is a composite number and ...
0
votes
1answer
26 views

Quadratic congruence prime numbers [on hold]

If $p$ is a prime number... a) show that $x^2 \equiv 1 \pmod{\!p}$ has only the following solutions: $x \equiv 1 \pmod{\!p}$ and $x \equiv -1 \pmod{\!p}$. b) show that $(p-1)! \equiv -1 ...
-1
votes
1answer
33 views

Is $\pi(y)\pi(x+k)\ge\pi(x)\pi(y+k)$? [on hold]

Is it true that for some fixed $k\ge2$ and for all sufficiently large $x$ and $y$ with $y\ge x$ we have, $$\pi(y)\pi(x+k)\ge\pi(x)\pi(y+k)$$ where $\pi(x)$ is the prime counting function. I am ...
0
votes
0answers
31 views

Are these elementary assertions about quadratic intervals and prime factors true?

Assertion 1: Every quadratic interval is an even number from 2 to infinity. The interval size does not include the interval endpoints, $x^2$ and $(x+1)^2$. Therefore, every interval size is an even ...
1
vote
1answer
29 views

Counting the number of integers $x$ in a sequence of $30a$ consecutive integers where $\gcd(x(x+2),30)=1$ and $p \mid x(x+2)$ where $p \ge 7$

I was writing a computer program and I found that for all sequences that I tested the number of $x$ in a sequence of $30a$ consecutive integers for a prime $p$ is less than or equal to: ...
0
votes
0answers
25 views

Series with prime number second method

Today I made an exercise in which I had to prove that : $$\sum_{n \ge 1} \frac{1}{p_n} $$ where $p_n$ is a prime number ($p_1=2$) is divergent. Well it was really difficult and at the end of the ...
0
votes
0answers
22 views

Does this 'alternating' series with $\Lambda(n)$ converge for all $\Re(s)>0$?

The following equation is well known and valid for $\Re(s)>1$: $$\log\big(\zeta(s)\big)=\sum_{n=2}^\infty \dfrac{\Lambda(n)}{\log(n)\,n^s}$$ where $\Lambda(n)$ is the Von Mangoldt function. Take ...
2
votes
1answer
26 views

Prove that powers of any fixed prime $p$ contain arbitrarily many consecutive equal digits.

Prove that powers of any fixed prime $p$ contain arbitrarily many consecutive equal digits. It is an intuitive re-statement of Baltic Way 2012 (I think there are shortlists in Baltic Way every ...
5
votes
0answers
91 views
+50

Geometric average of prime gaps?

The aritmetic average of prime gaps around $x$ is $\ln(x)$. What is the geometric average of prime gaps around $x$ ? Does that strongly depend on the conjectures about the smallest and largest gap ...
6
votes
1answer
102 views

How to prove that $a=z^{p}$ for some $z \in \mathbb{Z_{+}}$?

Claim : If for a positive, composite integer $a$ and an odd prime $p$, such that $\gcd(a,p)=1$, we are given $$ a^{p^{n-2}(p-1)} \equiv 1 \pmod {p^n} \ \forall \ n \geq 2 \ \ ;\ ...
1
vote
1answer
23 views

If $p$ is an odd prime with $(p - 1)/2$ primitive roots, is $p$ a Fermat prime?

If $p$ is an odd prime and there are $(p - 1)/2$ primitive roots modulo $p$, then is $p = 2^k + 1$ for some nonnegative integer $k$? This is the converse of a statement that I have already ...
1
vote
3answers
81 views

Do all prime numbers satisfy $p \mid (p-1)! + 1$? [duplicate]

If $m > 1$, $m \mid (m-1)! + 1$, then we can get the conclusion that $m$ is a prime number. But if we have a prime number $p$, can I get $p \mid (p-1)! + 1$? (I verify it when $p < 100000$, and ...
0
votes
1answer
47 views

Prime Numbers Primer [on hold]

This may not the appropriate site—but I thought Academia SE would be less appropriate. I'd like to begin working towards the ability to discover something novel about prime numbers. That is, I want ...
1
vote
1answer
23 views

How to efficiently list prime with a very specific property

I noticed that my phone number 06 xx xx xx xx is a prime number. Ok that cool ... But if you had the country code (+33 for france), ...
4
votes
2answers
96 views

odd prime numbers

For $m \geq 4$, set $P_m$ to be the set of all odd prime numbers strictly less than $m$ that do not divide $m$. For example, $P_4=\{3\}$, $P_7=\{3,5\}$, $P_{15}=\{7,11,13\}$. Now, for $n \geq 1$, ...
3
votes
2answers
37 views

Arithmetic progression - terms divisible by a prime.

If $p$ is a prime and $p \nmid b$, prove that in the arithmetic progression $a, a+b, a +2b, $ $a+3b, \ldots$, every $p^{th}$ term is divisible by $p$. I am given the hint that because ...
2
votes
0answers
34 views

The name given to the number 1 in the context of Primes and Composites

We give names to the sets of numbers called Primes and Composites. Is there a name for the number 1, in this context, seeing it is neither a Prime or Composite?
2
votes
2answers
37 views

Is there a ring - homomorphism $\mathbb{F}_p \rightarrow \mathbb{F}_q $ (p,q prime , $p \not= q$ )?

So we have two prime fields and seek a homomorphism between them. I assume that i have to find a homomorphism that is valid for all p,q prime , $p \not= q$, not just one for each choice. I would say ...
2
votes
0answers
64 views

Can I use integer frequencies in quadratic intervals to set a lower bound for primes? [closed]

I want to find out if the following arithmetic approach could produce a backdoor proof of Legendre’s Conjecture. There are two assumptions, Questions A and B, which are posed in the text and labeled ...
2
votes
0answers
25 views

Prime distribution around Riemann counting function

Is it true that the primes are normally distributed around the Riemann counting function $R(n)$ as a folded CDF? (Scaled $p_n-R(n)$)
0
votes
2answers
20 views

Proof that every quadratic residue has two roots, modulo a prime

Can someone provide a proof that every quadratic residue, when working in $\mathbb Z_p$, where $p$ is a prime, has exactly two roots? Indeed, there cannot be only one root as for any $a^2$, we know ...
3
votes
3answers
49 views

Number Theory Simple Proof

I am looking at a solution for a problem where the following line is stated but not explained, and I can not seem to make sense of it: If a prime $p\equiv 3\pmod 4$ then why is $\frac{p(p+1)}{2}$ ...
6
votes
2answers
471 views

Is this a meaningful approach to primes?

Motivation: I tend to be good at recognising patterns and I saw one with factorial: $$ n! = \prod_{i=1} p_i^{J(n,p_i)} $$ where $p_i$ is the $i$'th prime and $$ J(n,i)= \sum_{S=1}^\infty [n/i^S] $$ ...
-4
votes
0answers
30 views

Finding the modulo of 801 [closed]

If $d_{k}(m)$ is the number of divisor of m that are congruent to $k$ modulo $4$. How can I find $d_{1}(801)$ and $d_{3}(801)$ .
1
vote
1answer
31 views

Highest ratio between consecutive prime numbers

Let r = p2/p1; where p1,p2 are consecutive prime numbers. What is the highest possible value of r? is there any consecutive prime numbers such that r > 5/3?
2
votes
0answers
32 views

Question about the Chinese Remainder Theorem and the residue class ring ${\bf Z}/p\# {\bf Z}$

In a question that I asked on MO, Terence Tao observed that: The Chinese Remainder Theorem tells us that the residue class ring ${\bf Z}/p\# {\bf Z}$ is isomorphic (as a ring) to the product of ...
1
vote
2answers
333 views

Aren't there obvious patterns in the primes that no one makes use of and what about this…

Let's take the sequence of naturals at or above two ($2, 3, 4, \dotsc$) and cross out just the primes $2$ and $3$, as well as all their multiples: $$\require{cancel}\cancel{2}, \cancel{3}, \cancel{4}, ...
4
votes
2answers
64 views

Find the smallest $N$ such that $\sum_{k=1}^N\frac{1}{p_k}>\pi$. (The $p_k$'s are the prime numbers.)

How to solve the following problem? Let $\{p_k\}_{k=1}^\infty$ be the set of primes (in increasing order). What is the smallest integer $N$ such that $$\sum_{k=1}^N \frac{1}{p_k}>\pi?$$ We ...
10
votes
4answers
367 views

Understanding the trivial primality test

I'm reading an algorithms book and I came across a code example for a primality test. The problem is that I couldn't understand the condition for the for-loop: ...
3
votes
1answer
55 views

Find all odd positive integers $n$ greater than $1$ such that for any coprime divisors …

Find all odd positive integers $n$ greater than $1$ such that for any coprime divisors $a$ and $b$ of $n$, the number $a + b − 1$ is also a divisor of $n$. This was taken from the Russian ...
2
votes
1answer
39 views

Question on Furstenberg topology on Z and P subspace of primes

Hi all I was given this question: I have Z (the integers) with the Furstenberg topology on it, i.e. the topology induced by non constant arithmetical progressions presented here, and I am asked to ...
3
votes
2answers
33 views

Contradicting $p|n $s.t $p > \sqrt n$

I have proved a basic theorem in prime numbers, If $n \ge 2$ and $n$ is composite, then it is divisible by some prime $p \le \sqrt n$. This is a fairly basic result, and then my textbook shows me how ...
7
votes
0answers
102 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
1
vote
3answers
32 views

Basic question about modular arithmetic applied to the divisor sum function $\sigma(n)$ when $n=5p$

While studying the divisor sum function $\sigma(n)$ (as the sum of the divisors of a number) I observed that the following expression seems to be true always (1): $\forall\ n=5p, p\in\Bbb P,\ p\gt ...
2
votes
1answer
64 views

Most Common Difference Between Two Consecutive Primes?

The question is as stated in the title. I was given this interesting problem by a friend of mine, but I don't know how to proceed with a solution. The immediate thought I had was that the most common ...
1
vote
2answers
42 views

If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime?

The Statement of the Problem: If $n \in \mathbb N$, under what conditions are $n$ and $n+2$ relatively prime? My Thoughts: I know that the answer is that $n$ must be odd. However, I'm not sure how ...
3
votes
0answers
44 views

Are there any known special properties of a number located between twin primes?

With the exception of $4$, every number located between twin primes is divisible by $6$. This one is obvious, but are there any other properties that can be ascribed to such numbers? A property may ...
2
votes
2answers
84 views

A miraculous number N

Of course we can talk about 1 digit prime numbers, 2 digit primes , 3 digit primes , and so on..., my question is : is there an N (N greater than zero) such that there are no N-digit prime numbers ? I ...
2
votes
1answer
67 views

Using Fermats prime numbers to prove that there is infinitely many prime numbers

A Fermat number $F_n$ is of the form $F_n = 2^{2^n} + 1$ Furthermore, $F_n = 2 + F_0F_1F_2......F_{n-1}$ Now I already proved that if $n \neq m$ then $\gcd(F_n,F_m) = 1$ Here is the proof Without ...