New answers tagged

0

Suppose $n + 1$ is odd. Let $a$ be a real number such that $|a| \neq 1$. Then $X = \sum_{k=0}^{n}a^{2k} = \frac{a^{2(n+1)} - 1}{a^{2}-1} = \frac{a^{n+1} - 1}{a - 1} \cdot \frac{(-a)^{n+1} - 1}{(-a) - 1} = \sum_{k=0}^{n}a^{k} \cdot \sum_{k=0}^{n} (-a)^{k}$.


3

And since you have asked this question, here is an interesting piece of information, that in the sequence $101,10101,1010101,....$ none of the numbers are prime EXCEPT the first one. This can be proved quite easily and in your case the number is $${{(10^{4034}-1)}/99}$$, and the numerator can be written as $${{(10^{2017}}-1)} \times {{(10^{2017}}+1)}$$ and ...


10

Note that $1010101....10101$ is $\frac{10^{4034}-1}{99}$. Also, $10^{4034}-1$ is $(10^{2017}-1)(10^{2017}+1)$, both of which are larger than $99$. This implies that the number is not prime.


0

I just wanted to supply a specific quote from a text that defines prime numbers for negatives in the way that several of the other answers already affirm. This is from Hungerford's Abstract Algebra: An Introduction (sec. 1.3): DEFINITION. An integer $p$ is said to be prime if $p \ne 0, \pm1$ and the only divisors of $p$ are $\pm1$ and $\pm p$. ...


0

You should be aware that some texts do in fact define primality for negative numbers (and not just $-1$). For example, the following development is from Hungerford's Abstract Algebra: An Introduction (sec. 1.3): DEFINITION. An integer $p$ is said to be prime if $p \ne 0, \pm1$ and the only divisors of $p$ are $\pm1$ and $\pm p$. EXAMPLE. $3, -5, ...


3

I've written the program Akiva Weinberger suggested above. This is just a straightforward interpretation of the sieve of Eratosthenes, in R. n = 30092 top = 2*n isPrime = rep(TRUE, top) isPrime[1] = FALSE nextprime = 2 while (nextprime < sqrt(top)){ isPrime[seq(2*nextprime, floor(top/nextprime)*nextprime, nextprime)] = FALSE nextprime = ...


4

According to Wikipedia, $${x\over\ln x-1}\lt\pi(x)\lt{x\over\ln x-1.1}$$ for large $x$, with the lower bound holding for $x\ge5393$ and the upper bound for $x\ge60184$. Thus the inequality $\pi(2n)\lt2\pi(n)$ holds for $n\ge30092$, since the inequality $${2n\over\ln(2n)-1.1}\lt{2n\over\ln n-1}$$ holds for all $n$ (i.e., since $\ln2\gt0.1$). Whether the ...


2

For small numbers the easiest way is to do trial division. Try to divide it by every prime up to $ \sqrt{n} $ where n is the number you are checking. For a 4 digit number you will need to check at most 25 numbers.


1

One sure shot way is to Check if it is divisible by any prime number below $\sqrt{n}$ where n is the number. That's what any optimal computer program does.


1

When talking about primes it can be useful to know that mathematicians divide the integers into four types. Following are the four types and their definitions. First, there's zero. It's in a class by itself. It's special because it's the additive identity. Second, there are units. A unit is any number that is a divisor of 1. (Why 1? Because it's ...


1

Possible but not very interesting without more conditions. Totally trivial example: $$\Gamma(x+1) = 2^{\log_2\Gamma(x+1)}\,3^0\,5^0\cdots$$ Another almost trivial example: rewrite the product $$\Gamma(x) = \frac{e^{-\gamma x}}x\prod_{n=1}^\infty(1+x/n)^{-1}e^{x/n}$$ as $$\prod_{n=1}^\infty p_n^{\text{something}_{p_n}(x)}$$


2

a reason why $$n!=\prod_{p}p^{\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^{2}}\rfloor +.. } $$ is that $$\ln( \lfloor x \rfloor ! ) = \sum_{k \le x} \ln k$$ thus $$\zeta'(s) = -\sum_{n=1}^\infty n^{-s} \ln n = -s\int_1^\infty \left( \sum_{k \le x} \ln k \right) x^{-s-1}dx = -s\int_1^\infty \ln( \lfloor x \rfloor ! )x^{-s-1}dx = ...


0

You could also use Mertens' 3rd theorem which states that $$ \lim_{n\to\infty}\log n\prod_{p\le n}\left(1-\frac1p\right)=e^{-\gamma}\;. $$


2

To answer the first part, this is a valid manipulation of integrals. To answer the second, there aren't many interesting statements logically equivalent to "$p$ is prime". Yours suffers from a big problem: $a$ and $b$ are integers. Integrals, and calculus in general, really doesn't care about integers, so it doesn't seem like a good place to go looking for ...


1

(E) is correct. But you should not forget about the case where a and b are non-natural divisors of n, so $\not \exists \{a,b\}\subset \mathbf{N}, \ldots$


2

Apart from $2$, $3$, $5$ and $7$, every prime number must be relatively prime to $210$. Between $1$ and $210$, there are $\varphi(210) = 48$ numbers prime to $210$. Whether a number is relatively prime to $210$ depends only on its remainder modulo $210$. Therefore for all $k \geq 1$, we have $\pi(210k) \leq 48k + 4$. For any number $n \geq 1$, there is some ...


1

At first I thought it was a palindromic prime. There are lots of variations, and the largest currently known has 474,501 digits (Wikipedia seems to be out of date -- see The Prime Pages). For the top 3, they have some form M+1 where M is mostly factorable, hence a BLS75 n-1 proof can be done. We can find palindromic primes of this sort with lots of tools, ...


2

Out of any three numbers chosen of the form $ p, p+2, p+4$. One of them will be a multiple of three. Here's the reasoning for this. Out of any three consecutive numbers, one of them has to be a multiple of 3. If none of them were a multiple of 3, then it implies there are two consecutive multiples of three separated by a distance greater than three ! Out ...


1

For $Re(s)> 1$ we have the Euler product $$ \frac{1}{\zeta(s)}=\prod_p (1-p^{-s}). $$ Taking the limit $s\to 1$ shows that the infinite product $\prod_p (1-\frac{1}{p})$ is $0$, since $\lim_{s\to 1}\zeta(s)=\infty$. A second possibility is to use that the product $\displaystyle\prod_{n=1}^{\infty} (1- a_n)$ is non-zero if and only if $\sum_{n=1}^{\infty} ...


5

$x = 3^n, y = 2^n$ $$ 3 x^2 + x y - 4 y^2 = (3x + 4y)(x - y)$$


0

"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number." - point is that prime numbers are defined as natural numbers so the question is not relevant! Source: Prime Numbers


2

There is a pattern yes. And it follows from the fact that prime numbers cannot be factorized further. The basic idea for checking is - 1)prime factorize n. 2)If all prime factors have an even power, then n satisfies the required condition. Often when we say "pattern", we are either looking for something which is intuitive like an AP or GP. Or else, we ...


5

Let $n\in \mathbb N$. Then $$\sqrt n \text{ is rational} \iff \sqrt n \text{ is integer} $$ Proof: Suppose $\sqrt n = \frac{p}{q}$ is a rational number in lowest terms , so $p,q>0$ and $\operatorname{gcd}(p,q) = 1$. Then $n = \frac{p^2}{q^2}$, and $\operatorname{gcd}(p^2,q^2) = 1$ And since $q^2$ divises $p^2$, $q^2 = 1$, so $q = 1$ Therefore $\sqrt n=p$ ...


0

For any real number $n$: if $n$ is square of a rational, then $\sqrt{n}$ is rational. Otherwise, it's irrational. Can you apply this to your case ($n$ - positive integer)?


7

It can be proved prime using Elliptic Curve Primality Proving; I checked using Primo which only takes a few seconds. How they found it? The process probably was: Make a list of interesting-looking numbers. Filter the list using trial division. On the remaining numbers, use a fast pseudo-primality test (e.g. Fermat's test). Check the ones that pass the ...


13

Your logic argument for $-1$ being the only negative prime: $-3$, for example, could not be prime because it is equal to $3\cdot(-1)$ $-1$, however, is prime because it is divisible only by itself and by $1$ According to this logic, $+1$ is the only positive prime, since: $3$, for example, could not be prime because it is equal to $(-3)\cdot(-1)$


6

If you think negative numbers are weird, try imaginary numbers. There's not really a good way to think of positive numbers. You could say an imaginary number is positive if its real part is positive, but then you still get results like $(1+2i)(1+2i) = -3+4i$ so you immediately lose the fact that the product of two positive numbers is positive. That means ...


2

Instead of primes, consider the set $S = \{p^{2^n} \space\vert\space n,p \in \mathbb{N}, p \space \text{prime}\}$. These are the primes as well as the squares of primes, fourth powers, eighth powers, etc. Every positive integer can be represented uniquely as a product of distinct elements of $S$, in other words multiplication is a bijection between ...


50

If we define prime so that $-1$ is prime, unique factorization into primes fails, since $6=3\cdot 2=3\cdot 2\cdot (-1)^2$. So it is not useful to define $-1$ as a prime. When we get to higher math, we find that when we talk about "primes" in other systems, we are required to treat any pair of numbers that divide each other as "equivalent." That is, if $a$ ...


1

$2^p-1$ is prime implies $p$ is prime. Not the other way around, that is, not every prime $p$ makes $2^p-1$ a prime. For now, there's no way to generate an arbitrary large prime, hence the record of largest prime. The reason we try to find prime of the form $2^p-1$ is partially because of how the computers are designed (working on bits $0$ and $1$).


5

No, a Mersenne prime is a number $m$ such that $$m = 2^n -1$$ is prime. Then $n$ is also prime.


0

So if $p_j|Q$ then $Q=p_jq$ for some integer $Q$. Looking at $Q-p_1p_2...p_j...p_n=p_j(q-p_1p_2...p_n)=1$ you see that there is a factor $p_j$ on the left-hand side times another integer, so $p_j$ would have to divide $1$. That is a contradiction, so no such $p_j$ can exist.


2

Suppose $Q=p_j \cdot N$ for a natural number $N$. Then $$Q- p_1p_2 ..p_{j-1}p_jp_{j+1}.. p_n = p_j(N-p_1p_2..p_{j-1}p_{j+1}..p_n)$$ and $p_j$ divides $Q-p_1..p_n$, but this is the number $1$.


0

If we are trying to quantify the proportion of composites on an interval after removal if primes in the sieve-like way you describe, the following applies. You can prove without too much difficulty that the proportion P(k) of composites on the interval $[1,p_k\#]$ is $$P(k)=1-\prod_{i=1}^k(1-1/p_i), $$ and with a little more effort that this ratio ...


0

The OP's proposed proof of infinitely many primes with digital roots $1,4,7$ is not complete (although the conclusion follows from Dirichlet's Theorem just as for digital roots $2,5,8$). The idea was inspired by Euclid's proof of the infinitude of primes. We consider the expression: $$ b = p_1\cdot p_2\cdot p_3\cdot \ldots\cdot p_n + 1 $$ where ...


3

Any sequence $F_n$ of pairwise coprime integers will contain infinitely many primes, because each new $F_n$ has a new prime factor, for all $n\in \mathbb{N}$. In your example, $n=15,16$, but we have infinitely many $n$.


2

For digital root say $2$, use the fact that there are infinitely many primes of the form $2+9k$. This is a consequence of Dirichlet's Theorem on primes in arithmetic progressions.


-1

How about "Every number has possible prime factors up to its square root. Thus every $q$ has possible prime factors between the largest prime used to create it and it's own square root."?


1

Hint: one of the three numbers $p$, $p+2$, $p+4$ must be divisible by $3$.


4

Hint: Assume you have found such a prime, and then look at divisibility by some small, other prime.


3

$$10181^4 + 1 = 2 \cdot 17 \cdot 1657 \cdot 4657 \cdot 5113 \cdot 8009$$


1

Proth's theorem allows very fast proofs for numbers of the form $k \times 2^n+1$ ($k$ odd, $k < 2^n$). Lucas-Lehmer-Riesel allows fast proof for numbers of the form $k \times 2^n-1$ ($k < 2^n$). There were some press releases (e.g. these at MersenneForum) that briefly describe the process of how they were found. It was a distributed computing ...


1

I believe it's unknown if there is an algorithm that can compute a prime larger than $N$ in polynomial time (that is, $O((\log{N})^k)$ for some k). Cramér's conjecture implies that exhausitive search (counting up from $N+1$ and testing with AKS) runs in polynomial time.


1

Sum of reciprocals of prime numbers less than $m$ is roughly $f(m ) = \ln( \ln(m))$ up to a constant (I don't know any elementary proof of this fact though) .Now note that $n$-digit numbers are just numbers between $10^{n-1}$ and $10^n$, so you are looking for $f(10^n) - f(10^{n-1})$. This doesn't quite match with your observation though.


5

This is a consequence of Polignac's conjecture. It also implies the twin prime conjecture. Therefore your conjecture is intermediate in strength between those two.


3

Multiply the numerator by $p$ to get $\binom{p}{k}$, a natural number and note that the denominator can't have $p$ as its factor.


0

As provided by vrugtehagel`s comment, there are no closed forms, and more information can be seen in the link he provided. However, here is one solution that is always guaranteed to be true. Since you merely have to find $k$ to solve this equation, you just have to find $k$ such that $pk \equiv r \pmod q$. You use Euler`s Theorem, and set $k$ to ...


5

Legendre's conjecture is reported by Wikipedia to be that for each $n$ there is a prime between $n^2$ and $(n+1)^2$. That would imply $$ \lfloor \sqrt{p_{n+1}} \rfloor - \lfloor \sqrt{p_n} \rfloor \le 1. $$ For example, $\lfloor\sqrt{173}\rfloor=13$ and $\lfloor\sqrt{167}\rfloor = 12$. Obviously in many cases the difference between integer parts of the ...


4

I think Mathmo123 already gave the Best Answer (and the one which deserves the bounty), and I understand your trepidation at dealing with quartic domains. But I also think you were a bit too hasty to drop the quartic domains line of inquiry, even though it still leads to a quadratic domain as the answer. For now I'm going to ignore the special case $a = b = ...


0

There is no answer which you can understand right now because you are too young and your knowledge is too little to follow a proof of Bertrand's postulate. You can do the following: Begin to read elementary number theory from the beginning.(It is a very difficult part of Mathematics do not be disappointed , give yourself some time) The fact that you are only ...



Top 50 recent answers are included