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

3
votes
3answers
84 views

Is this formula: $81n^2+135n+97$ wealth by prime numbers which $n$ is natural number?

I made some effort to set a wealth quadratic formula for prime, I found this formula: $A(n)= 81n^2+135n+97$, it gives primes for $n=0 $ to $n=18 $. I would be like some one to show me if this really ...
1
vote
1answer
31 views

Easy (?) estimation about prime powers

Let $N_k$ be some integers with $\sum_{k\mid n}kN_k=p^n$. How can I prove $$\frac{p^n}{n}-\frac{2p^{n/2}}{n}\leq N_n?$$
3
votes
1answer
89 views

Why doesn't the equation have a solution in $\mathbb{Q}_2$?

I have to find for which primes $p$, the equation $x^2+y^2=3z^2$ has a rational point in $\mathbb{Q}_p$. According to my notes: Obviously, $\forall p \in \mathbb{P}, p \nmid 2 \cdot 3$, there is a ...
0
votes
0answers
15 views

Use of Prime Power Factorization

I think that I may not be understanding the use of prime decomposition of integers: If two integers $a=p_1^{j_1}...p_n^{j_n}$, $b=p_1^{k_1}...p_n^{k_n}$ are factored into primes, $b|a$ iff $k_i \leq ...
53
votes
13answers
11k views

Why is Euclid's proof on the infinitude of primes considered a proof?

I've expressed Euclid's proof on the infinitude of primes on Mathematica: ...
4
votes
1answer
122 views

Question about Paul Erdős’ proof on the infinitude of primes

I was reading Julian Havil’s book Gamma where he talks about a short proof by Paul Erdős on the infinitude of primes. As I understand it, here are the steps: (1) Let $N$ be any positive integer and ...
3
votes
1answer
94 views

Primes Number Theory

For which primes $p$ is $2^p+1$ divisible by $p$? What I have been doing is: $2^p+1\equiv 0\pmod p$ $2^p\equiv -1\pmod p$ Then by Fermat's Theorem, we get $2^p\equiv 2\pmod p$ This shows ...
1
vote
0answers
52 views

The sum of consecutive odd primes has at least three prime factors, not necessarily distinct [on hold]

Given the odd primes $3, 5, 7, 11, 13, 17, 19,\ldots, 2n-1$, prove that if $p$ and $q$ are adjacent odd primes in this list, then $p + q$ necessarily has $3$ prime factors. We do not require the ...
2
votes
3answers
55 views

Proof of non divisibililty of $\binom{n}{r}$ with a prime $p$

I came across this : "It is possible to show that if $p$ is prime, $\binom{n}{r}$ is not divisible by $p$ if and only if the addition $r + (n-r)$, when written in base $p$, has no carries. This means ...
1
vote
3answers
54 views

Infinitely many primes of the form $6n - 1$

Prove there are infinitely many primes of the form $6n - 1$ with the following: (i) Prove that the product of two numbers of the form $6n + 1$ is also of that form. That is, show that $(6j + 1)(6k + ...
1
vote
0answers
28 views

Solutions $n^2 = -1 \mod (p_n-1)$

Consider the equation $n^2 = -1 \mod (p_n-1)(*)$ where $p_n > n$ and $f(n) = p_n$ is the largest prime that satisfies the equation. $f(n)$ gives $p_n$ assuming there is a solution to the equation ...
6
votes
5answers
802 views

Can this number theory MCQ be solved in 4 minutes?

The Problem: ( 270 + 370 ) is divisible by which number? [ 5, 13, 11 , 7 ] Using Fermat's little theorem it took more than the double of the indicated time limit. But I would like to solve it quickly ...
8
votes
1answer
156 views
+50

Sequences for that $\sum_{n} \frac{1}{x_n}$ is divergent and $\sum_{n} \frac{1}{x_n \ln x_n}$ is convergent

We will denote with $(x_n)$ a given sequence and we introduce the following two series. $$S^* = \sum_{n} \frac{1}{x_n} \quad \text{and} \quad S_* = \sum_{n} \frac{1}{x_n \ln x_n}.$$ We know that if ...
0
votes
1answer
28 views

Proving a statement similar to the Fermat's theorem using modular arithmetic.

I have to prove that if m > 1 and not a prime, then $\exists a,b,c \in \mathbb{Z}$ such that $c \not= 0 (\mod m)$, $ac = bc (\mod m)$, but $a \not = b (\mod m)$. I am sorry I don't know how to put ...
0
votes
0answers
22 views

Fermat Prime Numbers Coprime [duplicate]

Fermat numbers are shown by: $F_m = 2^{2^m} + 1$. How can I prove that for any $m ≠ n$, I can have $(F_m, F_n) = 1$, or coprime?
0
votes
1answer
25 views

Infinite Prime Numbers: With Fermat Numbers

Suppose that the Fermat numbers $F_m$ are pairwise relatively prime. Can someone help me prove, given this, that there are infinitely many primes.
1
vote
1answer
35 views

A theory of radicals of integers?

It seems to me that radicals, natural numbers without power factors, generalize the concept of primes. You could ask after the nth radical and the number of radicals less than a specified number. But ...
7
votes
2answers
305 views

Consecutive numbers that share the same sum of prime factors

Let $f(n)$ denote the sum of the prime factors of $n$ (with multiplicity). I have been looking for pairs of consecutive numbers $n,n+1$ such that $f(n)=f(n+1)$. Case #$1$: ...
3
votes
5answers
57 views

Manually obtainining a list of primes $\leq n$, by using the root of n?

In my abstract math class I learned that if we want to get a list of primes $\leq n$ manually, we have to calculate the root of n, and the floor of that result will be the greatest number for which to ...
5
votes
1answer
153 views

Primes in a group: number theory

Characterize the primes for which 3 is not a square in $Z_p$. Compute $T_{17}$ where $T_p:=\{a+\sqrt{3}b:a^2-3b^2=1\} \subset Z_p[\sqrt{3}]$. Compute $T_{17}$. What are the orders of each of the ...
2
votes
3answers
122 views

number theory proof

Does this proof work? Prove or disprove that if $\sigma(n)$ is a prime number, n must be a power of a prime. Since $\sigma(n)$ is prime, $n$ can not be prime unless it is the only even prime, $2$, ...
19
votes
4answers
1k views

Are primes randomly distributed?

There is a famous citation that says "It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990) I have this very ...
1
vote
1answer
26 views

Series involving primes

Trying to find an asymptotic bound for the series $$ S(x) =\sum_{p\leq x}\frac{\varphi(p-1)}{(p-1)p} $$ as $x \rightarrow \infty$. Of course $$ \frac{\varphi(p-1)}{p-1} =\prod_{q\mid ...
1
vote
1answer
105 views

Primality Criterion for Specific Class of Proth Numbers

Is this proof acceptable ? Theorem : Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $3 \mid k $ , and $\begin{cases} k \equiv 3 \pmod {30} , & \text{with }n \equiv 1,2 \pmod 4 \\ k ...
2
votes
1answer
27 views

sucessive primes with distance greater than k

I am studying bounds in prime gaps and I would like to gather as much information as I could. I am just an undergraduate student, it's not a very important project, I am just doing it by curiosity. I ...
6
votes
3answers
105 views

Elementary proofs of prime gap theorems?

"Obviously" it is thrue that $p_{n+1}<2p_n$. Testing for $n<10$ shows it is true for small $n$ and no mathematician or wannabe has ever doubt that it is true for big $n$. But there is no real ...
1
vote
4answers
138 views

Proving that $p_1p_2\mid n$ iff $p_1\mid n$ and $ p_2\mid n.$

Let $p_1$, $p_2$ be distinct primes. Using the Fundamental Theorem of Arithmetic prove that a natural number $n$ is divisible by $p_1p_2$ if and only if $n$ is divisible by $p_1$ and $n$ is divisible ...
32
votes
5answers
646 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$ $${F_{n}}^2 - 28$$ cannot be a prime. I came to this accidentally while trying to solve another ...
4
votes
5answers
734 views

Properties of the euler totient function

Why is it that the euler totient function has the following condition true based on its definition? $$ \phi(p^k)=p^{k-1}(p-1) = p^k(1-\frac{1}{p}) = p^k-p^{k-1} $$ A proof would be awesome and an ...
13
votes
1answer
790 views

Finding smallest and largest prime factor of $\frac{200!}{180!}$

I originally started off by listing all the primes: $p<200$ then trying to calculate the prime factorisation of each (which I realise is a silly thing to do) I believe there must be a simpler way ...
1
vote
1answer
73 views

How did Gauss discover the prime number theorem?

Carl Friedrich Gauss conjectured in his early youth that $$\lim_{x \rightarrow \infty} \frac{\pi(x)}{x/\log(x)} = 1.$$ Any idea how did he reach such result?
4
votes
5answers
697 views

Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
2
votes
5answers
630 views

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. [duplicate]

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. This is what I got so far. I figured that since $p,q$ are bigger than $5$, there are only odd primes for this conjecture. ...
-1
votes
1answer
177 views

Proof for Goldbach's Conjecture [closed]

There is a proof given here. I couldn't find any flaw in it, what's wrong with it?
2
votes
0answers
83 views

$f(x)\sim 1/x \implies (1+f(x))^x\to e$, but what family of functions maximizes the speed of convergence from below?

This problem is subordinate to finding out if $$\left(1+\frac{\log p_{n+1}}{p_n}\right)^{p_{n+1}/\log p_n},$$where $p_n$ is the $n$-th prime, never stabilizes above or below its limiting value, which ...
6
votes
0answers
70 views

Applying iterated function on the sum of the squares of the prime factors of $30$

Let $f(n)$ denote the sum of the squares of the prime factors of $n$ with multiplicity. For example, $f(60)=f(2\cdot2\cdot3\cdot5)=2^2+2^2+3^2+5^2=42$. Denote the iterated function ...
0
votes
0answers
38 views

Divisibility of a power sum by a prime

For a given prime $p>2$ and positive integer $k$, let $$S_k=1^k+2^k+...+(p-1)^k$$ We have to find the values of $k$ for which $p|S_k$. By the binomial theorem we know that $p|i^k+(p-i)^k$ when $k$ ...
3
votes
1answer
56 views

How find prime numbers $p_{i}$ such $p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$ is square number

Question: Let $n\ge 5$ be an odd number, show that: there exist (or does not exist) primes $p_{i}\:;\:i=1,2,\cdots,n$ such that $$p_{1}+p_{2},p_{2}+p_{3},p_{3}+p_{4},\cdots,p_{n}+p_{1}$$ all ...
7
votes
4answers
75 views

Are there infinitely many quintuples of type $p, p + 2, p + 14, p + 26, p + 38$?

Are there infinitely many quintuples of type $p, p + 2, p + 14, p + 26, p + 38$? I think there are not... but I don't know exactly why this isn't true. My homework isn't requiring that I formally ...
2
votes
2answers
100 views

Clarify a problem with prime and composite numbers

What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a positive composite integer? The solution listed says The requested number $\mod {42}$ ...
3
votes
3answers
38 views

Find all the positive integers $m$ such that $p_{m}≥2m$

Find all the positive integers $m$ such that $$p_{m}≥2m$$ where $(p_{m})$ is the sequence of prime numbers I have no idea to start.
5
votes
0answers
118 views

Primes as sum of squares.

If $p_{i}$ and $p_{j}$ are two primes of the form $4k+1$ , with $p_{j} > p_{i}$, show that if $p_{j} \neq$ sum of two squares $p_{i}$ is also not equal to sum of two squares. It is well ...
1
vote
1answer
30 views

Need help with notation — finite set of random primes

I need help with notation for a finite set of random primes. Edit I've inserted my take on the format from the answer. Does it work? My attempt:$$\{X\in\binom{\mathbf P_{3,100}}{20}\},$$ ...
0
votes
1answer
33 views

are there infinitely many primes in Fibonacci sequence

There is one proof about infinitude of prime with following method, http://www.ams.org/mathscinet-getitem?mr=2271540 Also it is well know that any two consecutive Fibonacci numbers are mutually ...
13
votes
3answers
444 views

Prove that $n^2+n+41$ is prime for $n<40$

Here's a problem that showed up on an exam I took, I'm interested in seeing if there are other ways to approach it. Let $n\in\{0,1,...,39\}$. Prove that $n^2+n+41$ is prime. I shall provide my own ...
0
votes
1answer
29 views

Prime dividing multinomial [closed]

Let $p$ be a prime. I was wondering for what numbers $a_1,\ldots,a_p$ such that $a_1 + \ldots + a_p = p$ that $p\mid\binom{p}{a_1,\ldots,a_p}$?
1
vote
1answer
72 views

If $a_n$ is prime then $n$ is prime too

Given sequence $(a_n)$ : $a_1=1, a_2=4, a_3=15, a_n=15a_{n-2}-4a_{n-3}$. Prove that if $a_n$ is prime then $n$ is prime too. It is easy to prove that $a_n=4a_{n-1}-a_{n-2}$ and ...
0
votes
3answers
32 views

Nonzero quadratic residues modulo 101

How many Nonzero quadratic residues are there modulo prime 101 I am lost where to start to my knowledge there is no formula for number of quadratic residues a prime has It will be too much to start ...
1
vote
0answers
38 views

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation?

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation? $2$ is the only prime with $1$ one, the Fermat ...
-1
votes
2answers
58 views

primes equal if and only if one divides other

$p,q$ primes. prove $p=q$ if and only if $p$ divides $q$. $p|q$ stands for '$p$ divides $q$' $p|q\Leftrightarrow p=q$ $\Leftarrow$: $p(1)=q$ and therefore $p|q$ $\Rightarrow$: if $p=\pm 1$, ...