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
0answers
46 views

Ulam's Spiral in multiple dimensions

I'm trying to get my head around Ulam's spiral in N Dimensions. Basically I'm looking for an algorithm where I can supply a dimension number N and it'll draw the spiral in N dimensions. I'm looking ...
4
votes
1answer
59 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): ...
4
votes
2answers
148 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 ...
0
votes
0answers
41 views

Solutions to polynomial congruence mod p

What are the values for prime $p$ s.t. the equation $$x^4 \equiv -1 \mod{p}$$ has solutions?
37
votes
5answers
3k 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
109 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
29 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
64 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
69 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
53 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
90 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 ...
0
votes
1answer
38 views

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

With the following Mathematica program: ...
11
votes
3answers
269 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
49 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 ...
4
votes
1answer
62 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 ...
0
votes
0answers
23 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
2
votes
0answers
53 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 ...
-2
votes
1answer
14 views

Defining a function/(operator?) which will give a prime nearest to the product

Is there a function/(operator?) which gives a prime nearest to the product of two whole numbers like $x*y=p$ +-$d $ where $p$ is the nearest prime to the product and $d$ is the difference between the ...
0
votes
2answers
32 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
34 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
56 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
61 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} - ...
2
votes
1answer
57 views

$px^2-2y^2=1$,for what p,the pell equation has the result

$p$ is a 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 it's ...
1
vote
1answer
61 views

Primes and infinite primes of the form

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
76 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 ...
0
votes
3answers
79 views

How many elements are in the invertible set Zn?

My question is directly, how many elements are in the invertible set Z35? It's my understanding that for any Zn, if n is prime, then the number of invertible elements is equal to n-1. In addition, ...
0
votes
0answers
36 views

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

Find prime factorization of the number $13$ in the ring $Z[\frac{-1+ \sqrt{3}}{2}]$ My progress: Let $w=\frac{-1+ \sqrt{3}}{2}$ and let $N(z)=z \bar z$ be the norm function. $N(a+bw)=a^2-ab+b^2$ ...
1
vote
1answer
51 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 ...
0
votes
1answer
34 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
42 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 ...
0
votes
0answers
22 views

Riemann R function - explanation

I am having trouble understanding Riemann's argument that leads to $R(x)$ as an asymptotic to $\pi(x)$: ...
1
vote
0answers
49 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 ...
5
votes
1answer
291 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
42 views

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

My progress: Let's take $a\in Z[\frac{-1+\sqrt{-3}}2]$ such that $a|2$, and function $l(x)=x \bar x$. $a|2$ $\Rightarrow$ $2=a*b$ $\Rightarrow$ $l(a*b)=l(a)l(b)=4=l(2)$ If $z \in ...
1
vote
1answer
37 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$ ...
1
vote
2answers
41 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
75 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 ...
0
votes
1answer
51 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
58 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?
1
vote
0answers
62 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: ...
0
votes
1answer
86 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
86 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
50 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 ...
1
vote
0answers
55 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 ...
20
votes
4answers
2k views

Sum of four squares not a prime

Let $ a, b, c, d $ be natural numbers such that $ ab=cd $. Prove that $ a^2+b^2+c^2+d^2 $ is not a prime. I am clueless on this one. I tried contradiction, but didn't get anywhere. Can you help? ...
2
votes
0answers
41 views

If there is an integer $n$ such that $n^2\equiv3\pmod p$, where $p$ is prime, prove there are integers $a$ and $b$ such that $|a^2-3b^2|=p$

If there is an integer $n$ such that $n^2\equiv3\pmod p$, where $p$ is prime, prove there are integers $a$ and $b$ such that $|a^2-3b^2|=p$. So $n^2-3 = pm$ for some integer $m$, and I know $|a^2 ...
0
votes
1answer
51 views

finding a unique integer using mod

Consider two different prime numbers $x$ and $y$. Show that the following is true: For every pair of numbers $m$ and $n$ so that $0\le m<x$ and $0\le n< y$, there is a unique integer $q$, where ...
7
votes
0answers
163 views

Cramér's Model - “The Prime Numbers and Their Distribution”

I was reading "The Prime Numbers and Their Distribution" by Gérald Tenenbaum and Michel Mendès France, the section about Cramér's Model, and I couldn't prove a couple of results. I would like to start ...
5
votes
1answer
65 views

Eigenvalues appear when the dimension of the Prime Index Matrix is a prime-th prime. Why?

I had a look at the eigenvalues of the matrix, I called it Prime Index Matrix (is there a better name?), constructed like the following: $$ P_{k,p_k}=P_{p_k,k}=1, $$ where $p_k$ is the $k$th prime. ...
0
votes
0answers
26 views

Why do we need the extra assertion in this question?

Proposition: Let $2^i$ be the highest power of 2 dividing m, let a be odd and assume that $x^{m} \equiv a\space (mod\space 2 ^ {2i+1}$ ) is solvable. Then $\forall$ $j \geq$ 2i + 1, $x^{m} ...