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
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
34 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
37 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
0answers
49 views

Prime pairs $(p,q)$,$\quad q=(n \quad mod \quad p)$ and $2p+q=n (odd)$. Is there a definition about them?

I am studying congruences and I have observed this kind of prime pairs $(p,q)$ related to odd numbers. Do this kind of prime pairs have a name or have been studied before? Here is the definition: ...
0
votes
1answer
44 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
22 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 ...
0
votes
1answer
1k views

finding the greatest perfect square dividing an integer

how can we find the greatest integer which is a perfect square and which divides an integer? I believe factorisation can be used here but am not sure how to get the result out of it for all prime, ...
-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 ...
6
votes
1answer
115 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 \ \ ;\ ...
3
votes
2answers
288 views

Do you know Legendre's conjecture ? Has it been proved?

Legendre's conjecture: proposed by Adrien-Marie Legendre, states that there is a prime number between $n^2$ and $(n + 1)^2$ for every positive integer $n$. Has it been proved?
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
43 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 ...
2
votes
0answers
73 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 ...
10
votes
3answers
1k views

For any $n$, is there a prime factor of $2^n-1$ which is not a factor of $2^m-1$ for $m < n$?

Is it guaranteed that there will be some $p$ such that $p\mid2^n-1$ but $p\nmid 2^m-1$ for any $m<n$? In other words, does each $2^x-1$ introduce a new prime factor?
4
votes
1answer
37 views

Is there an $n$ such that $p|n^2+1$ with $2n<p<2n+\sqrt n$?

Is there an integer $n$ such that $n^2+1$ is divisible by a prime $p$ with $2n<p<2n+\sqrt n$? It's complicated to describe my interest, but these are near-missed for arc-cotangent reducible ...
12
votes
2answers
1k views

Elementary proof of Zsigmondy's theorem

I've been writing a not-so-short introduction to elementary number theory, supplying proofs for all theorems. When coming across Zsigmondy's theorem, it seemed difficult to find a proof available on ...
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), ...
3
votes
3answers
2k views

About the factors of the product of prime numbers

If a number is a product of unique prime numbers, are the factors of this number the used unique prime numbers ONLY? Example: 6 = 2 x 3, 15 = 3 x 5. But I don't know for large numbers. I will be using ...
3
votes
2answers
39 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 ...
9
votes
3answers
3k views

Can Prime numbers be negative? [duplicate]

I was wondering, can a prime number be negative? We had a question over at security.se which stated that prime generation with openssl: openssl dhparam -text 1024 ...
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 ...
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}$ ...
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 ...
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] $$ ...
5
votes
1answer
101 views

With $N$ a constant $>0$, show $\prod_{p<x}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}$.

Related. Show that if $x$ is large enough,$$\prod_{\substack{p<x \\ p \ \text{prime}}}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}.$$ Speaking of which, Theorem 6.12, and maybe others, of this ...
3
votes
1answer
206 views

What is the sixth Martin quadruple $\sqrt[n]{x_1^k+x_2^k+x_3^k+x_4^k} =\text{Integer}$ for $k=1,2,3$?

Define a Martin quadruple {a,b,c,d} as a solution in non-zero integers to the system, $a+b+c+d = x^2$ $a^2+b^2+c^2+d^2 = y^2$ $a^3+b^3+c^3+d^3 = z^3$ It can be shown that there are an infinite ...
10
votes
4answers
373 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: ...
1
vote
2answers
48 views

If $30$ divides $p_1^4 + p_2^4 + \ldots + p_{31}^4$. Prove that $p_1=2$, $p_2=3$ and $p_3=5$.

Let $p_1<p_2<\cdots<p_{31}$ be prime numbers such that $30$ divides $p_1^4 + p_2^4 + \cdots + p_{31}^4$. Prove that $p_1=2$, $p_2=3$ and $p_3=5$. No clue how to start..Hints are welcomed.
1
vote
1answer
32 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
339 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 ...
0
votes
2answers
46 views

How to decide the randomness of a dataset by checking the prime numbers inside it?

So it is weekend! I am reading currently a book where I found this sentence: "71 percent of men said they had a 'good sense of direction'. Only 47 percent of women reported same thing.", and I thought ...
20
votes
1answer
451 views

(Unsolved) In this infinite sequence, no term is a prime: prove/disprove.

$ 343,~ 34343, ~3434343, ~343434343,\ldots$ $\begin{array}\\ \color{Red}{343} &\color{Red}{: 7^3}\\ 34343 &: 61\times 563\\ \color{green}{3434343} &\color{green}{: 3\times 11^2\times ...
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 ...
1
vote
3answers
33 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 ...
39
votes
3answers
3k views

Is $n! + 1$ often a prime?

Related to this question, I wonder how often $n!+1$ is a prime? There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not. Does anybody know more about it?
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 ...
5
votes
3answers
213 views

How do we identify twin primes .

as known , each prime number greater than 3 is of the form $6k-1$ or $6k+1$ . twin primes are all sort of two adjacent primes of difference $= 2$ as: $$(11,13) ,(17,19),\ldots,(6k-1,6k+1)$$ -Is ...
2
votes
1answer
84 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 ...