Prime numbers are natural numbers greater than 1 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
vote
0answers
118 views

Integration by parts of the Logarithmic Integral

I am doing work on analytic number theory, and I am currently looking at the Prime Number Theorem, that is $$\pi(x) \sim Li(x)$$ Some of my sources say that I can do integration by parts on the ...
0
votes
1answer
22 views

A conjecture about the existence of a member within an interval with certain divisibility conditions - counter examples?

Conjecture The interval of the natural number line $[ap_{n}, (a+1)p_{n}]$ contains a member $e$ that is not divisible by any prime number $p_{m}$ less than or equal to $p_{n}$, if $(a+1) \leq 4p_{...
2
votes
0answers
102 views

Is there any relation between prime numbers and $\sqrt 2$?

Is there any relation between prime numbers and $\sqrt 2$? Connection between primes and $e$ , $\pi$ are obvious and can be googled easily but unable to find connection between any square root.
0
votes
2answers
1k views

What positive integers has exactly n divisors, for n from 1 to 5

The question is : What positive integers has exactly (and prove your result) (a) one positive divisor; (b) two positive divisors; (c) three positive divisors; (d) four positive divisors; (e) five ...
1
vote
1answer
45 views

Divisibility problem with product of two primes

Be $n=pq$ a natural number product of two different primes $p,q$. Prove, that on the set $\{1.2,2.3,...,n(n+1)\}$ there are exactly 4 numbers divisible by $n$.
0
votes
2answers
55 views

Primes and Inverses of an integer

I have the following question which I do not understand. Here it is: Consider the primes $5$, $7$ and $11$ as n. For each integer from $1$ through $n - 1$, calculate its inverse. I do not ...
4
votes
1answer
480 views

Can the twin prime conjecture be solved in this way?

After some research, I have discovered that proving the statement; There exist an infinite number of positive integers K such that; $K \neq 6ab \pm a \pm b$ and $K \neq 6ab \mp a \pm b$ is ...
7
votes
2answers
151 views

Is there a $k$ for which $k\cdot n\ln n$ takes only prime values?

There exist some real $k$ such that $\forall $ integer $ n > 1$ the integer part of $ k *n\ln(n)$ is always prime?
2
votes
2answers
134 views

Unique number of numbers multiplied together

I'm sure this has been asked before, but how many unique numbers can be made from multiplying $4$ numbers, each between $1$ and $100$? My guess is the all numbers from $1$ to $100^4$ except those ...
0
votes
1answer
170 views

$a ≡ b $(mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$)

Verify that if $a ≡ b$ (mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$), where the integer $n = lcm(n_1 , n_2)$. Hence, whenever $n_1$ and $n_2$ are relatively prime, $a ≡ b$ (mod $n_1*n_2$)...
4
votes
1answer
78 views

Prime number that are recursively made up of other prime number — what is this called

I've noticed that some prime number are composed entirely of other prime numbers for example -- some have parents on the left hand side (all the numbers below are prime): ...
6
votes
2answers
345 views

Proving the falsity of the Riemann Hypothesis

The Riemann Hypothesis is equivalent to the statement: $$|\pi(x)-{\rm li}(x)|\le \frac {1}{8\pi}\sqrt {x}\log (x)\text { for all }x \geq 2657,\text{ (Schoenfeld, 1976)} $$ Which can be visually ...
49
votes
5answers
5k views

Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can ...
2
votes
1answer
213 views

What numbers can be expressed with the following expression?

Given $\displaystyle \frac{a^3 - b^3}{c^3 - d^3}$, where a,b,c and d are distinct prime numbers, which integers can be expressed? Somebody asked this elsewhere online and it is beyond my abilities. I ...
1
vote
1answer
108 views

Algorithms for non-random but equidistributed ways to fill up a Cartesian plane

In pages 90-91 of this book the authors talk about uniform, but not necessarily normally distributed random ways to fill up a Cartesian grid. For example, in the attached images. These are the ...
4
votes
0answers
83 views

A question about powers of prime numbers

Can someone help me in this problem? Let $p,q$ be prime numbers with $p < q$. There exists $m \in \mathbb{Z}^+$ for which $1+p+p^2+...+p^m$ is a power of $q$. There exists $n \in \mathbb{Z}^+$ ...
2
votes
1answer
155 views

How to disprove the statement…

Statement: There are an infinite number of primes of the form 4N+1 and a finite number of primes of the form 4N-1. How would you disprove this ?
2
votes
0answers
138 views

Riemann prime counting function / Log Integral

I include the beginnings of an investigation: $$\text{A plot of R}(x)\text{ against }\pi(x):$$ $$\text{A plot of li}(x)\text{ against }\sum_{n=1}^{x}\frac{\pi(x^{1/n})}{n}:$$ It seems as though ...
6
votes
1answer
261 views

How to compute the mean average exponent of the naturals? What is the limit for large numbers?

With a friend I was trying to get an understanding for why the expected gap between primes is logarithmic. With that motivation I tried to express the average exponent of numbers. By average ...
1
vote
1answer
64 views

Why do the first spikes in these plots point in opposite directions?

With the following Mathematica program: ...
12
votes
3answers
318 views

Divergence for $p$ prime numbers and convergence for $m$ composite numbers

Does there exist a sequence $(a_n)_{n\in \mathbb N} \in \mathbb C^{\mathbb N}$ such that : For all $p$ prime numbers the series $\displaystyle \sum_{n\in \mathbb{N}} a_n^p$ diverges, and for ...
1
vote
1answer
54 views

$a$ modulo ${\prod_{i}p_i}$ where $p_i$ are primes.

This may be a very simple question for many of you. But somehow I can not see how to find a good way to answer this. The question is that if it is given that $$a\equiv k_i\mod{p_i},\quad i=1,2,\cdots,...
4
votes
1answer
121 views

Who generates the prime numbers for encryption?

I was talking to a friend of mine yesterday about encryption. I was explaining RSA and how prime numbers are used - the product $N = pq$ is known to the public and used to encrypt, but to decrypt you ...
3
votes
0answers
153 views

Probability distribution of the (size of the) smallest prime factor

Related question: Expected smallest prime factor Background: Given a toolbox of factorization algorithms (like trial division, ECM, quadratic sieve, GNFS) and a set of large composite numbers, I'm ...
0
votes
2answers
53 views

Let $p$ be a prime. Prove that $\sum_{a=1}^{p-1}(\frac{a}{p})=0$ ( Legendre symbol)

Let $p$ be a prime. Prove that $\displaystyle\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0$ I'm lost on this one. Any help would be appreciated
0
votes
0answers
41 views

How small can we make a modulus and still perform linear algebra on these pairs?

We can work with numbers of the form $(a^n + a^m)$, where $a$, $n$, and $m$ are all naturals, and $-v \le m \le v$ and $-v \le n \le v$. There is one more possibility: $a^n$ could be replaced by $0$, ...
1
vote
0answers
94 views

Is this wave noisy at prime powers and silent at composite numbers?

Mathematica knows that: $$\log(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\left(1 - \frac{1}{n^{(s - 1)}}\right)$$ And the von Mangoldt function should then be: $$\Lambda(n)=\lim\limits_{s \...
4
votes
1answer
75 views

Property of primes / property of other sequences?

Conjecture If we have two consecutive prime numbers $p_{n}$ and $p_{n+1}$, and another arbitrary prime number $p_a$ such that $p_{n} < p_{n+1} < p^2_{a}$, then it follows that $p_{n+1} - ...
3
votes
1answer
85 views

For which primes $p$ does $px^2-2y^2=1$ have a solution?

Let $p$ be an odd prime. If $px^2-2y^2=1$ is solvable, we can get Jacobi symbol $(\frac{-2}{p})=1$, so $p=8k+1,8k+3$. But when $k=12$, $p=97$, the Pell equation $97x^2-2y^2=1$ is unsolvable. I think ...
1
vote
1answer
113 views

Primes and infinite primes of the form $29 + 72k$

can you give the validity or proof of the following statements of my observations on Primes? $(1)$ For a positive integer $k$, there exists infinitely many primes of the form $29 + 72k$. $(2)$ If the ...
3
votes
3answers
396 views

Find all perfect squares of the form $17p + 1$ where $p$ is a prime.

So this is what I have, and I know it is incomplete. I know $p = 19$ is the only prime for which $17p + 1$ is a perfect square but I can't seem to find the connection. Proof. That is, $$17p + 1 = (x +...
1
vote
3answers
2k views

How many elements are in the invertible set $\mathbb{Z}_n$?

My question is directly, how many elements are in the invertible set $Z_{35}$? It's my understanding that for any $Z_n$, if $n$ is prime, then the number of invertible elements is equal to $n-1$. In ...
1
vote
2answers
219 views

Find prime factorization in the ring $\mathbb{Z}\left[\frac{-1 + \sqrt{3}}{2}\right]$

Find prime factorization of the number $13$ in the ring $\mathbb{Z}\left[\frac{-1 + \sqrt{3}}{2}\right]$ My progress: Let $w = \frac{-1 + \sqrt{3}}{2}$ and let $N(z) = z \bar z$ be the norm ...
1
vote
1answer
155 views

Fermat's little theorem proof by Euler

I am reading a book, it explains the Euler's proof of Fermat's little theorem (FLT). There are 3 theorems are presented to prove FLT, I understood the first two (I will skip the proof of each theorem)...
0
votes
1answer
45 views

Convergence of a modified sum of prime reciprocals for all $s \in \mathbb{C}$?

It is known that $\displaystyle \sum^\infty_{p \in \mathbb{P}} \frac{1}{p^s}$, with $\mathbb{P}$ the set of primes, only converges for $\Re(s) > 1$. The following sum of primes seems to converge ...
0
votes
1answer
49 views

How large is the largest prime required to satisfy these requirements?

I require a set of primes, all being equal to or greater than $2v+2$. The product of the primes should be at least $(2^v)+1$. I have one additional constraint. Each prime minus one must be ...
13
votes
2answers
351 views

Let $p$ be prime and $(\frac{-3}p)=1$. Prove that $p$ is of the form $p=a^2+3b^2$

Let $p$ be prime and $(\frac{-3}p)=1$, where $(\frac{-3}p)$ is Legendre symbol. Prove that $p$ is of the form $p=a^2+3b^2$. My progress: $(\frac{-3}p)=1 \Rightarrow$ $(\frac{-3}p)=(\frac{-1}p)(\...
1
vote
1answer
129 views

Probability of Relatively Prime Integers

A number theory paper I wrote was recently rejected from a journal due to "working under the untenable hypothesis that the natural density behaves like a probability measure (as it is not $\sigma$-...
10
votes
1answer
505 views

A club for some special prime numbers: new members welcome

Given an integer $i$, find an integer $n$ ( $2^{j-1}\le n <2^j$), and a prime divisor $p$ of $M_n=2^n-1$, so that $v= j+i$; where $p$ is written as $k2^v+1$, $k$ odd. In other words, $j$ is such ...
0
votes
2answers
84 views

Show that 2 is a prime in the ring $\mathbb{Z}\left[\frac{-1 + \sqrt{-3}}2\right]$

My progress: Let's take $a \in \mathbb{Z}\left[\frac{-1 + \sqrt{-3}}2\right]$ such that $a \mid 2$, and function $l(x) = x \bar x$. $a \mid 2$ $\Rightarrow$ $2 = ab$ $\Rightarrow$ $l(ab) = l(a)l(b) =...
1
vote
1answer
93 views

Co-primality of coefficients of coprime integers

Given that $a,b$ are co-prime, we have infinitely many solutions for $x,y$ to the equation $$ax+by=c.$$ Furthermore, solutions have the form: $x=ca^{-1}+tb,y=cb^{-1}-ta$. Given that $c$ can ...
1
vote
2answers
48 views

How can you show this relation between primes and roots of unity?

If $p$ is a prime number, how can you show that there are exactly $p^{n-1}(p-1)$ primitive $p^n$-th roots of unity? I am a little stuck on how to begin this proof. Do you need to use orders or ...
0
votes
1answer
93 views

Show $x^2+y^2 \equiv1\pmod p$ has $p-1$ solutions if $p \equiv1\pmod4$ and…

Question: Show the equation $x^2+y^2 \equiv1\pmod p$ has $p-1$ solutions if $p \equiv1\pmod4$, and $p+1$ solutions if $p \equiv 3\pmod4$ I'm really stuck on this one. Any help would be highly ...
3
votes
2answers
261 views

How to understand Apostol's proof of the irrationality of $\sqrt{n}$ if $n$ is not a perfect square?

Recently I am reading the textbook of Apostol, Mathematical Analysis, Second Edition. On page 7, there is a theorem 1.10: If $n$ is a positive integer with is not a perfect square, then $\sqrt{n}$ is ...
2
votes
1answer
75 views

Show that $m=6k+5$ has at least one prime divisor of the form $6n+5$

What's the best way of approaching this kind of questions?
4
votes
0answers
95 views

How to get the period of oeis.org/A130166 other than by trail?

oeis.org/A130166 a(0)=1; a(n)=prime(mod(a(n-1),1000)) starts with: ...
1
vote
1answer
176 views

A question about prime divisors of Mersenne number $M_n= 2^n-1$ when $n$ is odd

Is this true that a prime divisor of a Mersenne number $M_n = 2^n-1$ when $n$ is odd, cannot be a Proth prime (i.e. a prime number of the form $2^mk+1$, where $k<2^m$)? If yes, how is it ...
2
votes
3answers
379 views

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$. I could not approach the problem at all. I have no idea how to try the problem. Please help.
1
vote
2answers
77 views

$\mathbb{Q}$ adjoining primes and the sum of root of those primes

I have $p$, $q$ as primes, and I want to show that $\mathbb{Q}(\sqrt{p},\sqrt{q})=\mathbb{Q}(\sqrt{p}+\sqrt{q})$. I was thinking about using inclusion both ways, so what does an element in $\mathbb{...
1
vote
0answers
70 views

How to solve diophantine equation $\frac{x^p-y^p}{x-y}=n$

$$\frac{x^p-y^p}{x-y}=n$$ whit $p$ a prime greater than or equal to $3$,for what value to $n$, it's solvable and how to solve,and whether $\frac{x^p-y^p}{x-y}=q_1$ $\frac{x^p-y^p}{x-y}=q_2$ is ...