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

0
votes
2answers
62 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 ...
-3
votes
1answer
41 views

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

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}$$
1
vote
2answers
89 views

Understanding a proof showing 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 I asked it as a guest, and I could not comment on ...
-1
votes
3answers
54 views

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

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
75 views

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

How you 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 ...
2
votes
1answer
35 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 ...
1
vote
1answer
33 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
32 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
38 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
46 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. ...
2
votes
0answers
24 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
35 views

Quadratic congruence prime numbers [closed]

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
40 views

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

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 ...
1
vote
1answer
33 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
25 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
44 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 ...
16
votes
2answers
272 views

Geometric mean of prime gaps?

The arithmetic mean of prime gaps around $x$ is $\ln(x)$. What is the geometric mean of prime gaps around $x$ ? Does that strongly depend on the conjectures about the smallest and largest gap such as ...
6
votes
1answer
116 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
28 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
87 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
51 views

Prime Numbers Primer [closed]

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), ...
6
votes
2answers
151 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
40 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
40 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
75 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
29 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
21 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
51 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
473 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] $$ ...
1
vote
1answer
34 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
33 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
341 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
70 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
375 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
61 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
41 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
111 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
34 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
87 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
44 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
48 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
86 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
68 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 ...
4
votes
1answer
41 views

Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$. The hint was to use induction. ...
2
votes
2answers
46 views

Suppose $p$ is a prime number and $a$ is an integer. Show that if $p \mid a^n$, then $p^n \mid a^n$ for any $n \geq 1$?

I know that if $p \mid a^n$, I can say $a^n = pr$ for some integer $r$, you can also conclude that $\gcd(p, a^n) = p$, but I'm not sure how to use that information if I even can to show that $p^n \mid ...