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

2
votes
3answers
54 views

Why is it that if you square two prime numbers and add them, you get a number that is even and is not a perfect square?

If you do $x^2 + y^2 = n$ where $x$ and $y$ are both prime numbers and are both greater than $3$, why is $n$ always an even number that isn't a perfect square?
3
votes
1answer
45 views

Could all iterates of $s(n)=2n+1$ be composite for some starting $n$?

Let $s(n)=2n+1$ and $\sigma(n)=\{n,s(n),s^2(n),s^3(n),\ldots\}$, where $s^3$ denotes functions composition, $s^3(n)=s(s(s(n)))$. For example $\sigma(11)=\{11,23,47,95,\ldots\}$. As another example ...
0
votes
0answers
27 views

Reverse proof of Fermats Little Theorem [duplicate]

Let $n \in \mathbb{N}$. For all $x \in \{1,2,...n-1\}$ it is: $x^{n-1} \equiv 1 \text{ mod } n$. Show that $n$ is prime. This seems to be proving Fermat's little theorem the other way round. Until ...
0
votes
1answer
61 views

Are these two definitions of prime numbers equal?

In Coq for instance, prime numbers are defined ${n\ is\ prime} \doteq \forall a\in \mathbb{N}: a|n \rightarrow (a=1 \vee a=n)$ ...
0
votes
1answer
32 views

$\limsup_{n\to\infty}\frac{g_n}{\log^3 p_n} < \infty$?

The following quote comes from Wikipedia http://en.wikipedia.org/wiki/Prime_gap "Usually the ratio of $g_n / \log p_n$ is called the ''merit'' of the gap $g_n$;. In 1931, E. Westzynthius proved that ...
3
votes
2answers
72 views

Backwards proof of Fermat's Little Theorem

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$ This is basically Fermat's ...
9
votes
3answers
84 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
2
votes
0answers
48 views

A multivalued function $ f(x) = 0 $ with integer solutions $ x_1=p(n) $ and $x_2=q(n) $

Please help me to define a multivalued function $ f(x) = 0 $ with integer solutions : $ x_1 = p(n)$ and $ x_2 = q(n) $ such that $\dfrac{ p(n) + q(n) } { 2 } = 2 n + 1 $ and $ ...
5
votes
6answers
621 views

Polynomial with a prime number as a root

Is it possible to prove that this equation is false: $$ \sum_{i=0}^n a_i p^i = 0 $$ with following conditions: $a_i \in [-1;1]$; [Might $a\in\{-1,1\}$ have been intended here?] $p$ is a prime ...
9
votes
2answers
225 views

Yet another conjecture about primes

Let $\mathcal{N}(n)$ be the next prime greater than $n$. Conjecture: $\mathcal{N}(n!)-n!\:$ is either $1$ or a prime. It holds for n=1 to 99 and the expression is 1 for 3,11,27,37,41,73,77 and ...
2
votes
1answer
59 views

Number $N>6$, such that $N-1$ and $N+1$ are primes and $N$ divides the sum of its divisors

The perfect number $6$ is in the middle of the primes $5$ and $7$. It is the only perfect number with this property because odd numbers are not in the middle of two twin primes and even perfect ...
1
vote
2answers
47 views

Where can I find a list of large prime numbers

A repository of say 13 digit prime, 15 digit primes etc.
3
votes
1answer
56 views

Bounds for $n$-th prime

In this page I have found that the bounds for $n$-th prime is given by, $$n(\ln n+\ln \ln n)>p_n>n(\ln n+\ln \ln n-1)$$ for all $n\ge6$. Are there even stronger bounds for the $n$-th prime? If ...
1
vote
1answer
50 views

Upper bound on the maximal number of prime factors

I would like to prove $$\omega(n) \le \frac{\ln{n}}{\ln\ln{n}}$$ This is a quite standard result, but I haven't been able to find a proof. Here's what I've tried doing: ...
5
votes
1answer
48 views

weakened version of Dirichlet's theorem - proof without Dirichlet's theorem

Dirichlet's theorem states that arithmetic sequence with first term and common difference relatively prime, contains infinitely many prime numbers. Assume that we only want infinitely many numbers in ...
7
votes
1answer
82 views

Carmichael numbers of form $m^3+1$ and Ramanujan's $1729$

While researching for a post on tetranacci pseudoprimes I came across a list of Carmichael numbers, $$C_n = 561,\, 1105,\, 1729,\, 2465,\, 2821,\dots$$ Of course, Ramanujan's taxicab number $1729 = ...
2
votes
1answer
17 views

Division of the Binomial Coefficient

Prove that when p is prime, the binomial coefficient p!/(r!)((p-r)!) is divisible by p with r being greater than or equal to 1 and less than or equal to p-1 . Clearly p! is divisible by p so I cant ...
1
vote
3answers
39 views

Prove there exists $m$ and $k$ such that $ n = mk^2$ where $m$ is not a multiple of the square of any prime.

For any positive integer $n$, prove that there exists integers $m$ and $k$ such that: $$n = mk^2 $$ where $m$ is not a multiple of the square of any prime. (For all primes $p$, $p^2$ does not divide ...
10
votes
1answer
73 views

Mind-boggling property of a prime

As you have already probably known, an Emirp is a prime whose reversal give a different prime i.e: 37 is an Emirp because 37 is prime and its reversal 73 is also a prime, 79 is also an Emirp. Now I ...
2
votes
5answers
110 views

Prove the existence or the non-existence of a couple of numbers ($n$,$m$) such that $n^2=m!$ [duplicate]

In recent days, while I was doing exercises on combinatorics, I thought if a number $m!$ could be a perfect square. I proved to demonstrate it through the prime factorization. My attempt: ...
1
vote
0answers
53 views

What are the next few “tetranacci-like” pseudoprimes?

Starting with $n=0$: $k=2$ Given the roots $x_i$ of $x^2-x-1=0$. Then, we have the Lucas numbers, $$A_n = x_1^n+x_2^n = 2, 1, 3, 4, 7, 11, 18,\dots$$ The $n$ that divides $A_n-1$ are all the ...
0
votes
2answers
53 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
88 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
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 ...
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
30 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
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
1answer
45 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
23 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 ...
15
votes
2answers
242 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
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 \ \ ;\ ...
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
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 ...
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
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 ...