Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [prime-numbers]

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.

-1
votes
1answer
27 views

Obtaining Prime Numbers [on hold]

Is there a way to obtain all other prime numbers from a particular prime number ? If yes then how will it affect mathematics and other fields , if at all..? I mean , if I can give an expression where ...
2
votes
1answer
45 views

Proof: If no prime less than or equal to $\sqrt{n}$ divides $n$, then $n$ is a prime [duplicate]

I have the following theorem: If no prime less than or equal to $\sqrt{n}$ divides $n$, then $n$ is a prime. And the following proof (proof by contradiction) for said theorem: Suppose that no ...
3
votes
2answers
34 views

Let $t_1$, $t_2$,… $t_n$ is a sequence where $t_1=2$ and $t_{n+1}=t_n{^2}-t_n+1$. Prove that if $m\ne n$, then $t_m$ and $t_n$ are coprime.

Let $t_1$, $t_2$,$\enspace$.... $t_n$ is a sequence of natural numbers. The sequence is defined by these equalities - $t_1=2$ $\enspace$ and $\enspace$ $t_{n+1}=t_n{^2}-t_n+1$. $\enspace$ Prove ...
0
votes
0answers
17 views

How far was base $47$ checked for a generalized Wieferich-prime?

This question is closely related to : Wieferich primes in base $47$ but I would like to know the current search limit for this base. Upto which prime $p$ was $$47^{p-1}\equiv 1\mod p^2$$ verified ...
3
votes
1answer
28 views

Let $p$ be prime and let $r$ be a positive integer. How many generators does $\mathbb{Z}_{p^{r}}$ have?

Can someone please help me understand this solution? Let $p$ be prime and let $r$ be a positive integer. How many generators does $\mathbb{Z}_{p^{r}}$ have? I do not understand the part that is ...
1
vote
2answers
63 views

Primes of the form $\ \varphi(n)^{\varphi(n)}+n\ $ or $\ n^n+\varphi(n)\ $ for composite $n$?

This question : Do further prime numbers of the form $n^n+\varphi(n)$ exist? deals about prime numbers of the form $$n^n+\varphi(n)$$ I know no composite number $n$, such that this expression is ...
2
votes
2answers
55 views

Number 2 hasn't got this property, while all prime numbers do.

I am going to start with an example of two geometric figures. Rectangle must haves: quadrilateral four right angles opposite sides are equal and parallel diagonals bisect each other If we say that ...
-1
votes
2answers
181 views

How to calculate the number of digits in $2^{77232917} – 1$? [on hold]

The largest known prime numbers are often Mersenne primes, for example the largest as of December 2017 is $2^{77232917} – 1$. How can I calculate the number of digits in this number, and other ...
-2
votes
1answer
99 views

How to verify large Mersenne Primes [duplicate]

As of December 2017, the largest known prime number was the Mersenne prime $2^{77232917} – 1$. For such a large Mersenne prime, what are the techniques available for one to verify that it is in fact ...
0
votes
1answer
41 views

Find the three digit prime number.

What is the largest three-digit prime each of whose digits is a prime? - I believe it is 773, but correct me if I'm wrong.
2
votes
3answers
45 views

$P, Q$ and $R$ are prime numbers. $P + Q = R$ and $1 < P < Q.$ What is the value of $P$?

Attempt: $P + Q = R$ $P + Q - R = 0 $ $1 < P < Q$ $1 + Q < P + Q < 2Q$ $1 + Q < R < 2Q$ I am lost... The sum of two primes minus a third = 0 could be anything!
0
votes
1answer
61 views

Primes from Generalised Fermat Numbers [on hold]

Consider the number $(2m)^{2^n}+1$ where both $m$ and $n$ are positive integers. Can it be shown that for any given $n$, there exists an $m$ such that $(2m)^{2^n}+1$ is a prime number. Edit: It ...
5
votes
2answers
117 views

Is there a special name for primes $p = 2^n+1$ and what is the largest known to date?

I'm reading a paper by Pohlig and Hellman on computing discrete logarithms, they use primes $p = 2^n+1$ as a simple special case to explain their algorithm. I'm curious, is there a special name for ...
9
votes
5answers
799 views

Why multiplying powers of prime factors of a number yields number of total divisors?

Suppose we have the number $36$, which can be broken down into ($2^{2}$)($3^{2}$). I understand that adding one to each exponent and then multiplying the results, i.e. $(2+1)(2+1) = 9$, yields how ...
2
votes
2answers
68 views

Why does $f(x) = \sum_{n=1}^{\infty}(1/(x^{\mathrm{prime}(n)})$ have a local maximum?

We played around with https://en.wikipedia.org/wiki/Prime_constant this equation a bit and got to this by playing: $ y = f(x) = \sum_{n=1}^{\infty}\frac{1}{x^{\mathrm{prime}(n)}}$ where $\mathrm{...
2
votes
0answers
101 views

Do further prime numbers of the form $n^n+\varphi(n)$ exist?

Can the expression $$n^n+\varphi(n)$$ be a prime number for some integer $n>19$ ? For $n=1,2,3,19$ and no other positive integer $n\le 3\ 000$, the expression is prime. A further prime of the ...
2
votes
0answers
29 views

Finding Large Pseudoprimes with a Computer

I'm reading the book Prime and Programming and I'm stuck on one of the computer exercises. I'm checking for Fermat Pseudoprimes and I've written a program that works for reasonably small numbers, e.g....
-1
votes
2answers
95 views

Prime Sequences in Nature [on hold]

I've heard that prime numbers are considered to be important in the field of cryptography, however are there instances in nature where prime numbers emerge? I wonder if there any examples in nature ...
1
vote
1answer
50 views

A twin prime theorem, and a reformulation of the twin prime conjecture

In a previously posted question (A sieve for twin primes; does it imply there are infinite many twin primes?), I demonstrated that a sieve can be constructed that identifies all twin primes, and only ...
5
votes
1answer
1k views

Frequency of the Prime Numbers

Suppose I took all natural numbers less than or equal to $x$ and I picked one at random. Is there a way that we know of to express the probability that my number is prime in terms of $x$, for all $x$? ...
5
votes
1answer
54 views

Determine $2^{\frac{p-1}{4}}\equiv 1\pmod p$ or $2^{\frac{p-1}{4}}\equiv -1\pmod p$ when $p\equiv 1 \pmod 8$

Let $p=8k+1\equiv 1\pmod 8$ be a prime, thus $2$ is a quadratic residue module $p$. Euler's criterion show that $$2^{\frac{p-1}{2}}\equiv 1 \pmod p.$$ So we must have $$2^{\frac{p-1}{4}}\equiv \...
2
votes
0answers
28 views

Pell type equation about prime [duplicate]

Let $p=4k+1$ be a prime number such that $p=a^2+b^2$ , with $a$ an odd integer. Prove that the equation $$x^2-py^2=a$$ has at least a solution in $\mathbb{Z}$. Only a little progress (maybe useless): ...
1
vote
1answer
83 views

A sieve for twin primes; does it imply there are infinite many twin primes?

I have devised a sieve for identifying twin primes. My first question will be: Have I just rediscovered something already known? By comparing my sieve to the Sieve of Erastosthenes, I argue that there ...
0
votes
2answers
31 views

The definition of a prime constellation

On Mathworld http://mathworld.wolfram.com/PrimeConstellation.html it is first stated that a prime constellation is a sequence of k prime numbers, for which the gap between the last and the first ...
-1
votes
0answers
94 views

Proof for gcd(a^n + b^n,a-b) = gcd (a+b,a-b),given a>b and a,b are natural numbers

i found GCD( a^n+b^n , a-b ) = GCD(a+b , a-b) it is working on most of the cases, but i dont know if i am correct or not.Could anyone please provide proof of it.
1
vote
1answer
89 views

Alternating sum of inverse prime numbers [duplicate]

It is well known that the sum of all inverse primes is divergent. But the alternating sum is convergent by the Leiniz criterion. To which known constant "a" does the sum converge? $$a = \frac{1}{2} - ...
0
votes
1answer
53 views

Understanding part of derivation of Chebychev's Theorem

I cannot understand this result from pages 17–18 of Tenenbaum and Mendes's The Prime Numbers and Their Distribution on how the summation of $\frac{x\log(2)}{2^j}+O(\log(x))$ results in $2x \log(2) + O(...
3
votes
0answers
153 views

Is every positive integer greater than $2$ the sum of a prime and two squares?

I'm not sure if this conjecture is less hard than Goldbachs conjecture: any integer greater than $2$ is the sum of an odd prime and two squares of integers. Facts as: Every prime of the form $4n+1$ ...
2
votes
0answers
41 views

What does 3-PRP means exactly ? (in pfgw primality test)

When i do primality test for large integers with the software pfgw, it returns either composite or 3-PRP. 1: What does 3-PRP means exactly? 2: What is the error ratio? 3: When the test return ...
3
votes
1answer
85 views

An infinite number of primes in the sequence

Does the sequence $ a_n = \left|-\frac{n^4}{6}+\frac{3n^3}{2}-\frac{13n^2}{3}+6n-1\right|$ contain an infinite number of primes? I tried to find some theorems on this matter, but apparently the ...
-3
votes
1answer
56 views

If a number is not divisible by 2, 3 and 5, is enough to say that number is prime? [closed]

I'm Computer Science student. Last day, my teacher say this to the class room: "If a number is not divisible by 2, 3, and 5, mean that number is prime. This because odd numbers are divisible by 3 or 5,...
0
votes
0answers
47 views

Name of a property in number theory

I want to find the name (or author of the proof) on the following property: If $n\times m=\prod_i p_i$ where the $p_i$ are prime numbers, then $n=\prod_{i\in I}p_i$ for some subset $I$. I know it is ...
1
vote
1answer
48 views

Help proving $\sum_{pq \leq x} \log p\log q \frac{\log x}{\log pq} = \sum_{pq \leq x} \log p\log q + O(x)$

I'm reading Selberg, A. (1949). An Elementary Proof of the Prime-Number Theorem After deriving his formula: $$\sum_{p \leq x} \log^2 p + \sum_{pq \leq x} \log p \log q = 2x\log x + O(x)$$ The author ...
3
votes
1answer
93 views

$p >2$ is a prime, any facts about congruence relation between the class number of $Q(\sqrt p)$ and $Q(\sqrt{-p})$?

Let $p$ be an odd prime. This is a question about the class number of $Q(\sqrt p)$ and $Q(\sqrt{-p})$,which we denote by $h(p)$ and $h(-p)$ respectively. While doing my research on number theory I ...
0
votes
0answers
111 views

What is this divisibility pattern called?

Say I take the primes up to $P$, then there is a pattern of numbers that are divisible by those primes which is periodic every $k\cdot P\#$. What is this called, and is it symmetrical? Also, since ...
0
votes
4answers
31 views

if $b$ divides $ck$ and $b$ and $c$ are relatively prime, then $b$ must divides $k$

Suppose $b, c\in\mathbb{Z}$ and the greatest common divisor of $b$ and $c$ is $1$, i.e., $b$ and $c$ are relatively prime. If $b$ divides $ck$ for some positive integer $k$, then $b$ must divide $k$. ...
4
votes
2answers
151 views

A Proof of the Fundamental Theorem of Arithmetic

Is there a proof of the Fundamental Theorem of Arithemetic that does not make use of the Integers or Rational Numbers (as opposed to using only the Natural Numbers)? And if so, what is it? By the ...
6
votes
1answer
148 views

Upper and Lower bounds on the nth prime number

I know from papers like Dusarts's that $$n\left(\ln n +\ln \ln n -1+ \frac{\ln \ln n -2}{\ln n}-\frac{\ln^2 \ln n -6 \ln \ln n +12}{2 \ln^2 n}\right) \leq p_n \leq n\left(\ln n +\ln \ln n -1+ \frac{\...
0
votes
0answers
29 views

Jacobi symbol of sum of two squares

Say we have $x=a^2+b^2$. Are there any results regarding the Jacobi symbol $(\frac{x}{n})$, where $n=p*q$? Having $x'=a^2+c^2$, is there any connection between the Jacobi symbols $(\frac{x}{n})$ and $...
2
votes
1answer
80 views

An observation of prime number, not sure if this always hold

I have little math background and I just do some random observations on prime numbers and notice that: for $p > k$ where $p$ is a prime and $k$ is a positive integer: $$\sum_{i=0}^{k-1} 2^{ip} = 0\...
4
votes
0answers
63 views

When does an equation of the form ${1 \over p}{(2^{p-1}-1)} = 2pxy+x+y$ have no integer solutions?

Specific equations of the form below (for different given values of p, a prime number) will either have positive integer solutions for $x$ & $y$, or will not have any integer solutions. $${2^{p-1}...
4
votes
1answer
94 views

Reciprocity of different prime numbers can approximate $1$?

I want to see if there exist $p_1<p_2<p_3<\cdots<p_{1000}$ different prime numbers such that $|1/p_1+\cdots+1/p_{1000}-1|\le ({1\over p_{1000}})^2.$ a) what is my point with this? Nothing....
0
votes
0answers
44 views

distributions of prime numbers - theorem of Chebyshev

I was thinking: let $a\in(0,1]$, $1<b$ be given, and let $c$ be given as a positive integer. Can we find $N$ with the property that if $N$ is large enough, than the interval $(N^a,(b N)^a)$ always ...
2
votes
2answers
79 views

Is there a reason why the first few primes have hexagonal symmetry when snaked around the plane?

See the image. I've been playing around with some "space filling snakes" of sequences. This sequence is precisely the sequence of natural numbers. But when you snake it thusly, and color $1$ and ...
0
votes
2answers
104 views

Fermat Little Theorem [closed]

The problem I am trying to solve is how to use Fermat Little theorem to prove that the number 66013 is not prime. I found this problem on another website (Question Cove). The student who had to solve ...
0
votes
0answers
21 views

Quality of prime seeking methods

I am working on prime numbers with emphasis of prime search heuristics, and found the probabilistic methods for primes seeking, I am looking for a review of those methods quality in terms of machine ...
1
vote
1answer
49 views

On the sum of $\sum_{p \ prime} \frac{1}{p^2-1}$ [closed]

I was wondering whether there exists a closed form solution for $\sum_{p \ prime} \frac{1}{p^2-1}$?
2
votes
1answer
45 views

Odd amicable pairs

I was curious if there are odd amicable pairs such that both do not have a 5 in the ones digit? I apologize if it's easy to find one with a computer I'm not that smooth
1
vote
0answers
53 views

Plotting the sum of prime factors of integers with rational exponents [closed]

In a sense, some numbers other than integers can be written in terms of prime factors. For example $$ \sqrt[3]{\frac{1}{6^{5}}} = 6^{\frac{-5}{3}} = 2^{\frac{-5}{3}} \times 3^{\frac{-5}{3}} $$ We ...
0
votes
2answers
72 views

Find the largest power of 3 that divides $N =19202122…919293$. [closed]

Question All the numbers from $19$ to $93$ are written consecutively to form the number $N =19202122...........919293$. Find the largest power of $3$ that divides $N$. The following hint has been ...