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

25
votes
3answers
401 views

Can a number be equal to the sum of the squares of its prime divisors?

If $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then define $$f(n):=p_1^2+\cdots+p_k^2$$ So, $f(n)$ is the sum of the squares of the prime divisors of $n$. For which natural numbers $n\ge 2$ do we have ...
1
vote
2answers
85 views

The product of two prime numbers

I have two expressions (both of which have a term raised to the power of $n$) and I am trying to prove that they can't be prime numbers at the same time for $n>2$. I can't post the expressions, ...
1
vote
2answers
31 views

Is there a method to determine a prime number containing the first n digits?

For example, the number $10243$ is prime and contains the digits '0,' '1,' '2,' '3,' and '4.' Similarly, the number $20143$ is prime. Is there a method to determine whether a prime number exists ...
1
vote
3answers
30 views

Finding all the divisors of $a$ by decomposing it into the product $p^{\alpha_1}_{1} \cdot p^{\alpha_2}_{2} \cdots p^{\alpha_r}_{r}$

I'm trying to prove the following statement regarding the fundamental facts of prime numbers, but I don't really understand the relationship between $a$ and $b$. In order to find all the divisors ...
4
votes
0answers
63 views

What is the next prime with this form? [duplicate]

The following are primes, $$P_1 = 2^2 + 3^3$$ $$P_2 = 2^2 + 3^3 +5^5 + 7^7$$ After these two, the only prime of such form I've found is, $$P_3 = 2^2 + 3^3 + 5^5 + 7^7 + 11^{11} + 13^{13} +\dots+ ...
1
vote
2answers
66 views

Is this a valid equivalent expression of the twin prime conjecture?

The twin prime conjecture states basically that it is possible to find two primes $p$, $p+2$ at a distance $2$ that are as big as wanted (Wikipedia). I am learning about the basic properties ...
0
votes
0answers
76 views

What is this pattern in this calculation using primes?

So I was bored and when I get bored I write small programs that calculate something. This time I did this: I searched for the amount of primes bellow 10,000,000 using Sieve of Eratosthenes starting ...
7
votes
2answers
359 views

Efficient way to compute $\sum_{i=1}^n \varphi(i) $

Given some upper bound $n$ is there an efficient way to calculate the following: $$\sum_{i=1}^n \varphi(i) $$ I am aware that: $$\sum_{i=1}^n \varphi(i) = \frac 12 \left( 1+\sum_{i=1}^n \mu(i) ...
7
votes
6answers
2k views

what is Prime Gaps relationship with number 6?

Out of the 78499 prime number under 1 million. There are 32821 prime gaps (difference between two consecutive prime numbers) of a multiple 6. A bar chart of differences and frequency of occurrence ...
0
votes
3answers
515 views

How to determine if a number $A$ is divisible by all the prime factors of $B$?

How to determine if a number $A$ is divisible by all the prime factors of $B$? For example: $120,75$ $A=120=2^3\times3\times5$ and $B=75=3\times5^2$ Therefore yes, $A$ is divisible by the prime ...
-2
votes
1answer
20 views

inequality on Gaussian prime

Consider any Gaussian prime $p$ (except $|p|=\sqrt{2}$). If we have $|x|\leq|p|+0.5$, where $x$ is a nonzero Gaussian integer, can we prove $|x|\leq|p|$?
3
votes
0answers
60 views

Is there an advantage in using continued fractions for Catalan or Fibonacci-Lucas primality tests?

I am studying the basic theory about continued fractions and also reviewed here at MSE former questions to learn more. While reviewing the questions and answers, I found references to the Fibonacci ...
0
votes
3answers
73 views

The square of n+1-th prime is less than the product of the first n primes.

I wanted to prove the following question in an elementary way not using Bertrand postulate or analytic estimates like $x/\log x$. The question is $$ p_{n+1}^2<p_1p_2\cdots p_n,\qquad(n\geq4) $$ I ...
4
votes
0answers
134 views

A lower bound for an arithmetic function

Let $N \in \mathbb{N}$ such that $\phi(N) \sim N$, where $\phi$ is the Euler's totient function. Let $A \subset [N] := \{1, 2, \ldots, N\}$. For $n \in \mathbb{N}$ define the function $$ C_A(n) = \#\{ ...
2
votes
1answer
58 views

How to show $n$ is a prime number?

Let $a$ and $n$ be integers greater than 1. Suppose that $a^n-1$ is a prime. Show that $a=2$ and $n$ is a prime. What can you say about primes of the form $2^n+1$? By ...
1
vote
0answers
60 views

Are logarithms of prime numbers algebraically independent?

From Baker's theorem it follows that a linear combination of natural logarithms of prime numbers with non-zero algebraic coefficients can never be zero. Has it been proved that the set of all natural ...
8
votes
1answer
1k views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
1
vote
3answers
64 views

Upper bound for prime-counting function: $ \pi(n)\le\frac{n}{3}+2 $

$ \pi(n)\le\frac{n}{3}+2 $... Could someone explain me, how to prove it? I'm completely stuck, as informations I found on Wikipedia aren't very clear to me. (I was able to prove that for sufficiently ...
6
votes
3answers
185 views

Show that prime $p=4n+1$ is a divisor of $n^{n}-1$

Show that the prime number $p=4n+1$ is a divisor of $n^{n}-1$ Ok, the question itself is simple as hell, but I couldn't think of a simple way to solve this question. I tried to solve the ...
6
votes
2answers
334 views

Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every ...
0
votes
0answers
16 views

Prove that if $\ p^2 = a^2+2b^2 $ then $\ p = m^2+2n^2 $ (where a, b, m, n are integers, and p is prime) [duplicate]

Given that $\ p^2$ can be written in the form $\ p^2=a^2+2b^2 $ (where a & b are integers, and 'p' is a prime number), then prove that the prime number 'p' can also be written in the form $\ ...
6
votes
3answers
75 views

sequence of primes in arithmetic progression

The question is: Suppose $p_1<p_2<...<p_{15}$ is a sequence of prime numbers in arithmetic progression, with common difference $d$. Prove that $d$ is divisible by $2,3,5,7,11$ and $13$. Let ...
0
votes
1answer
34 views

Wieferich prime-Lang-Trotter conjecture connection?

Crandall-Dilcher-Pomerance prediction states that the number of Wieferich primes $<x$ is $log\ logx $ N.Katz in "WIEFERICH PAST AND FUTURE" states; The Crandall-Dilcher-Pomerance prediction is ...
31
votes
2answers
477 views

Proving that if $p^2 = a^2 + 2b^2$ then also $p$ can be written in form $a^2 +2b^2$

I'm high school student, and this problem has bothered me for about 2 weeks now. I don't necessarily need a solution, but for example mentioning a helpful theorem or property that could help me to ...
0
votes
2answers
43 views

Property of additive group [closed]

Let $m \in \mathbb{Z}_q$, for a prime $q$ and $x \in \mathbb{A}$, where $\mathbb{A}$ is an additive group of order $q$. Then is it always true that $mx \in \mathbb{A}$? If true, how to prove it? ...
1
vote
2answers
59 views

How many number id divisible by $p$ and is not divisible by any primes number which is less than $p$?

Let $N$ be a big integer. Let $p$ be a prime number. Is there a formula to count how many number less than $N$ such that they are divisible by $p$ and not divisible by any prime less than $p$. For ...
26
votes
1answer
308 views

Fibonacci $\equiv -1 \mod p^2$

Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify. EDIT: In response to ...
2
votes
1answer
163 views

Ulam spiral and triangular numbers

Is there any explanation for the twister-like pattern build by triangular numbers $$\Delta_n = \frac{n\cdot(n+1)}{2}$$ in the Ulam Spiral? Here for $1,\ldots,100$: Here's a picture with many more ...
1
vote
1answer
44 views

In the definition of Carmichael number, why is it necessary to have $(b, n) = 1$?

In number theory, a Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation $$b^{n-1}\equiv 1\pmod{n}$$ for all integers $1<b<n$ which are ...
0
votes
1answer
45 views

Sum of factors of multiplication of different numbers

Given $N$ numbers $n_i$ such that $\forall i \le N, n_i$ $\le10^9$, is there a method to calculate the sum of divisors of their product? For example, given $\{11,15,17\}$ their product would is ...
0
votes
1answer
55 views

Can a Carmichael number be even?

Can a Carmichael number be even? I know that a Carmichael number is a positive composite integer $n$ such that $a^n\equiv a \pmod n$ for all integer $a$. So what does I need to prove or disprove ...
0
votes
4answers
124 views

Euclid's proof of infinitude of primes.

http://en.wikipedia.org/wiki/Euclid's_theorem I just read Euclid's proof for the existence of infinitely many primes (I have never used his proof earlier to prove this). It seems to me that he ...
57
votes
8answers
6k views

The myth of no prime formula?

Terence Tao claims: For instance, we have an exact formula for the $n^\text{th}$ square number – it is $n^2$ – but we do not have a (useful) exact formula for the $n^\text{th}$ ...
2
votes
1answer
64 views

ABC conjecture consequence

At page 6 of the book: "Prime Numbers The most mysterious figures in Math" this statement is listed as one of the consequences of the ABC conjecture: There are Infinitely many Wieferich primes. This ...
3
votes
4answers
116 views

Find the smallest positive integer that ends in $17$, is divisible by $17$, and the sum of its digits is equal to $17$.

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with primes and composities but other than that, the textbook gave no hints ...
0
votes
3answers
73 views

Prime number equation

The number of solutions of the equation $xy(x+y)=2010$ where $x$ and $y$ denote positive prime numbers, is ____ I tried various things but nothing seems to work out. $2010$ can be resolved into ...
1
vote
2answers
47 views

Largest Arithmetic Sum of Relatively Prime Numbers Under 30

Pick however many integers in the range $[1,30]$ (inclusive). The only constraint is that all of these numbers must be relatively prime to each other. What is the largest possible arithmetic sum ...
9
votes
1answer
477 views

Primes and certain unit fractions [closed]

Are there primes $p,q$ and a natural number $a$ such that $\frac{1}{p}+\frac{1}{q}=\frac{1}{a}$?
0
votes
1answer
35 views

What does “421 is the smallest prime formed by the powers of two in logical order from right to left” mean and if so is it correct?

I've seen this on number gossip and a few other places, but I'm not exactly sure what it means. The only possibilities I have thought of for what they mean are "421 is the smallest center squared ...
1
vote
0answers
27 views

The asymptotic behaviour of triples $n!+q^{n!}=c$, where $q$ is the first prime greater than $n$, and abc conjecture

For a large positive integer $n$, let $q=q(n)$ (below we denote this $q=q(n)$ by $q_{N}$ because we assumed that is the $N$-th prime number) the first prime number which is (strictly) greater that ...
1
vote
1answer
45 views

What does the sum of the reciprocals of composites run along?

This is fairly straight forward: $$\sum_{p\space\text{prime}}^x \frac{1}{p_x} \sim \ln(\ln(x))$$ And if $$\sum_{c\space \text{composite}}^x \frac{1}{c_x}\sim f(x)$$ Then what is $f(x)$?
5
votes
1answer
238 views

Conjectured compositeness tests for $N=k\cdot 2^n \pm 1$ and $N=k\cdot 2^n \pm 3$

How to prove these conjectures ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ~\text{are ...
1
vote
2answers
64 views

Modulus and Fermat's Little Theorem

How do I calculate $ 11^{23} \bmod{163} $ using fermat's little theorem ?
0
votes
1answer
36 views

Counting how many primes exists between square root of a given range?

I am given with a range say l,r(1<=l,r<=10pow14).I am also given with cumulative count of primes no.'s that exists between 1 to 10pow7,e.g for 1,count=0(as no primes exists upto 1),for ...
2
votes
1answer
62 views

What is the smallest “prime” semiprime?

(All dots here means concatenation.) Let $s= ab$ be a semiprime number, then I call s a "prime" semiprime if all these following conditions are satisfied: The reversal of $s$ is a prime The ...
2
votes
0answers
52 views

Beal Conjecture and ($\bmod 3$) operation [closed]

When we apply a ($\bmod 3$) operation on the $A^x +B^y =C^z$ we will see some strange results. For e.g.: Let $A=6m+1$ & $B=6n+1$. Since $A$ & $B$ are odd numbers, $C$ will have to be even. ...
0
votes
2answers
72 views

The number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors

Prove that the number $2^{2^n} + 2^{2^{n - 1}} + 1$ can be expressed as the product of at least $n$ prime factors, not necessarily distinct. Doing what the hint has suggested, I have done the ...
6
votes
1answer
162 views

Number we know all prime numbers less than [duplicate]

We already know some very big prime numbers. ($2^{257,885,161} − 1$ as of time of writing is the largest known) It is my understanding, that we know it is a prime number but we don't know all prime ...
4
votes
1answer
108 views

Find the integral values for which $\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$

Let $\pi(x)$ be the prime counting function. The problem is, Find all integral values of $x,y$ such that, $$\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$$ I have no idea as to where to begin with. ...
3
votes
2answers
98 views

Is $\frac{2^{n-1}-1}{n}$ an integer only when $n$ is an odd prime?

I have the equation $$k = \frac{2^{n-1}-1}{n}$$ and wonder if $k$ is an integer when $n$ is an odd prime. The numerator is always odd, so even $n$ have no integer solutions. But when I run a test, it ...