Tag Info

New answers tagged

3

HINT: Clearly, when $n$ is even $n^4 + 4^n$ is even. When $n$ is odd, we have $$n^4+4^n = (n^2+2^n)^2 - \left(2^{(n+1)/2}n\right)^2 = \left(n^2+2^n+2^{(n+1)/2}n\right)\left(n^2+2^n-2^{(n+1)/2}n\right)$$


0

Here is another very different argument, which seems to work but only in one direction:$$x^{\underline n}=\prod_{i=0}^{n-1}(x-i)=(-1)^nn!\sum_{\sum_{i=1}^{i=n} {i.n_i=n}}\prod_{i=1}^{i=n}\frac{(-x)^{n_i}}{i^{n_i}n_i!}$$ The big sigma is over all the integer partitions of $n$, i.e. over all the n-uplets $(n_1,..,n_n), n_i\ge0$ such that $\sum_{i=1}^{i=n} ...


0

The most rapid way is to use the Abel's summation formula. If we put $a\left(k\right)=p $ if $k=p$ is a prime number and $0$ otherwise, we get $$\sum_{p\leq n}\frac{1}{p}=\sum_{k\leq n}\frac{a\left(k\right)}{k}=\frac{\pi\left(n\right)}{n}+\int_{2}^{n}\frac{\pi\left(t\right)}{t^{2}}dt. $$


0

Work in the polynomial ring $(\Bbb Z/p\Bbb Z)[x]$: in that ring $x^{\underline p}=x^p-x$, since both polynomials are monic of degree $p$ and have roots $0,\ldots,p-1$. Now just equate coefficients to get the positive part of the result. For the negative result, suppose that $n$ is not prime, let $p$ be a prime dividing $n$, and let $m=\frac{n}p$. Then ...


-1

Terrence Tao has proven that every odd number greater than one is the sum of at most five primes. Hence, using $3$ as a prime that we can substract to any even number greater than $5$, and noticing that $2$ is prime and $4=2+2$, every odd number is the sum of at most six primes. As a conclusion, every number greater than one is the sum of at most six ...


1

Don't worry, this is the easy direction of the Hasse principle (the other direction is much harder) -- you don't have to understand the Hasse principle to understand this. The point is that "addition and multiplication are well-defined mod $n$.'' So if $f(x_1, \ldots, x_n)$ is a polynomial with integer coefficeints, and $\alpha_1, \ldots, \alpha_n$ are ...


2

As pointed out in the other answers, the point is that there is no single-variable polynomial with integer coefficients which takes on only prime values - apart from constant polynomials. My preferred proof is: Suppose $f(x)$ is prime for all positive integer $x$. Take any value of $f$, say $p=f(1)$. The behavior of $f$ modulo $p$ is periodic, so since ...


3

Theorem 21 in Hardy and Wright's book on number theory reads No polynomial $f(n)$ with integral coefficients, not a constant, can be prime for all $n$, or for all sufficiently large $n$. The proof goes as follows. Replacing $f$ by $-f$ we may assume $f(n) \to \infty$ with $n$. So for some $N$, we know that $n > N$ implies $f(n) > 1$. Fix $x > ...


2

let $k=f(m)+m$ you can prove that : $$f(k)\equiv 0 \mod f(m)$$ In order to $f(k)$ to be prime we must have $f(k)=f(m)$ or $f(m)=1$, But $f(f(m)+m)-f(m)$ and $f(m)-1$ are two polynomials which have only finitely roots so there exists $x\geq A$ ($A$ any number you want) such that $f(k)\neq f(m)$ and $f(m)\neq 1$


0

Just take $m$ to be some multiple of $a_0$. Then everything will be multiple of $a_0$. Perhaps we have bad luck and $|f(m)|$ is in fact $a_0$... but it cannot happen for all the multiples of $m$ greater than 2010: simply consider that $f(x)=a_0+xg(x)$ with $g$ polynomial; if $x=m$ is $ka_0$, then $f(m)=(kg(ka_0)+1)a_0$, and $kg(ka_0)+1$ won't be $0$ or $-2$ ...


4

if $p$ is not $3$ then $\gcd(p,3)=1$ so $3$ divides $(p-1)(p+1)$ hence $3$ divides $p^2-1+3=p^2+2$ so $p^2+2$ is not a prime


2

You assumed $n$ being composite and reached a contradiction, namely $\frac{n}{k}<10^2$ dividing $n$. Hence, by the principle of proof by contradiction, $n$ is indeed prime.


2

The result of Yitang Zhang (and improved by James Maynard) in 2013 was that there exist infinitely many primes which differ by some fixed number $\leq 600$. This isn't helpful in your problem. The number of primes smaller than $n$ is given by the prime counting function, $\pi(n)$. It is known that $\frac{\pi(n)}{n/\log n} \to 1$ as $n \to \infty$, so ...


3

The smallest divisor of $n$ is at most $\sqrt{n}$. In your case, if $n$ has a non-trivial divisor, then it has a non-trivial divisor of at most $10^{3}=\sqrt{10^{6}}$.


1

This is a classical result of a course in analytic number theory. Chebyshev first showed that $$ c_1\frac{x}{\log(x)}\le \pi(x)\le c_2\frac{x}{\log(x)} $$ for all $x\ge 96098$, with the Chebyshev constants \begin{align*} c_1 & = \log(2^{1/2}3^{1/3}5^{1/5}30^{-1/30})\approx 0.921292022934, \\[0.3cm] c_2 & =\frac{6}{5}c_1\approx 1.10555042752. \\ ...


1

$ \forall i \in \{1,...,n-1\}\quad {n\choose i}$ is divisible by $n$ iff $n$ is a prime. Note that if $n$ is not a prime, then let $ n = p m$ where p is a prime. Then $$ {pm \choose p} = \frac{pm!} {p! (p(m-1))!}$$. So both denominator and numerator has p as a factor m times. So all the $p$'s cancel each other and the quotient is not divisible by $pm$.


1

Since for $n≠ 1,p$ where $p$ is prime, $$\binom{p}{n} = \frac{p(p-1)…1}{n!(p-n)!} ∈ \mathbb{Z} $$ and none of the factors in the denominator can divide $p$, this means that $p \left| \binom{p}{n}\right.$. If for example $p = 2q$ where $q>2$ is prime, then $$\binom{2q}{q} = \frac{2q(2q-1)…1}{(q!)^2} $$ then $q$ appears as a factor precisely 2 times on ...


3

$\def\ZZ{\mathbb{Z}}$I am really baffled by people coming on this site and writing very detailed conjectures about variants of the Pepin or Lucas-Lehmer primality tests, then claiming no theoretical background. (Prior examples 1 2 3.) How did you find this conjecture if you have no idea how these tests work? As we will see below, your test will correctly ...


0

Some partial results: By taking a large $p$, we see that $x\le y$. Let $d=y-x$. Assume $y>x$ (so certainly $y\ge 2$). If $p\mid y$ we obtain $x\bmod p\le y\bmod p=0$, hence $p\mid x$ and also $p\mid d$. Especially, $d\ge2$. Now Let $p$ be a prime dividing $x+1$ (which is $\ge 2$). Then $x\bmod p=p-1$ implies $y\bmod p=p-1$, i.e. $p\mid y+1$. Hence $d$ ...


2

Your statement needs to be more precise. The implication $\Rightarrow$ is obvious, if $n=p^2$ then it follows immediately from the definition or formula pf $\phi(n)$ that $n-\phi(n)=p$. For the converse, you need to be more precise. The way in which is stated, is correct but trivial: you are saying $n=p^2$ if and only if $n=p^2$ and $n=(n-\phi(n))^2$. If ...


1

Not if $x\neq y$. By the Fundamental Theorem of Arithmetic, they each have a unique factorization into primes, say $$x=p_1^{r_1}p_2^{r_2}\cdots,\\y=p_1^{s_1}p_2^{s_2}\cdots,$$ where these products are over all primes with all but finitely many $r_i$ and $s_i$ equal to zero. When $x\neq y$, we must necessarily have that $r_i\neq s_i$ for some $i$. If we have ...


3

Using the Stieltjes Integral and Integration by Parts yields $$ \begin{align} \sum_{p\le n}\frac1p &=\int_1^n\frac1x\,\mathrm{d}\pi(x)\\ &=\frac{\pi(n)}{n}-\frac{\pi(1)}{1}+\int_1^n\frac{\pi(x)}{x^2}\,\mathrm{d}x\\ &=\frac{\pi(n)}{n}+\int_2^n\frac{\pi(x)}{x^2}\,\mathrm{d}x \end{align} $$


2

the first thing to start with is the following, we call primes in order $p_1,p_2,\cdots \cdots$. Let $p_n$ the greatest prime less then or equal to $x$ (so as a consequence $\pi(x)=n$) then: $$\begin{align}\int_2^x \dfrac{\pi(u)}{u^2} du&=\sum_{i=1}^{n-1} \int_{p_i}^{p_{i+1}} \dfrac{\pi(u)}{u^2} du+\int_{p_n}^x \dfrac{\pi(u)}{u^2} du\\ \\ ...


1

This is really just a comment, but it's too long to post as such. Also, to a certain extent, it does address the OP's question, "what's going on here?" The function $f(k)=\mu a_k-k$, as the OP noted, is periodic. Its period is $$N=(2\cdot3\cdots p_n)-(1\cdot2\cdots(p-1))$$ (E.g., for $n=3$ the period is $N=(2\cdot3\cdot5)-(1\cdot2\cdot4)=22$, as can be ...


0

The formula you expressed holds always when p is a prime.(Fermat's Little Theorem). Lagrange's theorem is useful usually when dealing with the order of subgroups. How familiar are you with modular arithmetic? One way of describing "mod p" is that there are p possible remainders when dividing something mod p. For example, when dividing by 3, you could end up ...


0

It is very rare that the infiniteness or not of primes in such sparse sequences is known. Note that even for the very well-known Mersenne and Fermat numbers this is not known (for the former there are likely infinitely many prime, for the later likely not.) Heuristically (if I did not mess up my mental arithmetic) I think there should be infinitely many, ...


1

Let $g=p_{n+1}-p_n$ and write $p=p_n$ for simplicity. Then you're asking for $\log\log(p+g)-\log\log p$ which is $g/p\log p+O(g^2/p^2\log p).$ This Of course if you want $\sum_{k=1}^n\left(\frac{1}{f(k)}-\log\log p_k\right)=O(1)$ then $\sum_{k=1}^n\frac{1}{f(k)}\sim\sum_{k=1}^n\log\log p_k\sim n\log\log n.$ In fact $\log\log p_k=\log\log k+\log\log k/\log ...


2

Actually your set $\{1,3,7,9\}$ is correct. The interpretation is, first get one primitive root, say $2$; then take the powers of $2$ modulo $11$, corresponding to the numbers as indices. So we get $2^1=2; 2^3=8; 2^7=128\equiv7; 2^9=512\equiv6 $, we get the set $\{2,6,7,8\}$ mentioned by gammatester. (Actually this set will be the same even if we started ...


0

The primitive roots are the generators of $\mathbb{Z}_{11}^{*},$ which are $\{2,6,7,8\}.$ Check the $x$ from this set to give $x^{10} \equiv 1 \pmod {11}$ and lower powers are $\not \equiv 1,$ e.g. $2^{10}=1024\equiv 1 \pmod {11}$ and $2^{5}=32\equiv 10 \pmod {11}.\;$ Your set $\{1,3,7,5\}$ is wrong because e.g. $3^5 \equiv 1 \pmod {11}.$


1

You can consider the bounds, if $n$ sufficiently large, say for some $k>0 $ $$n\log\left(n\right)<p_{n}<n\log\left(n\right)+n\log\left(\log\left(n\right)\right) $$ then $$\sum_{n\geq k}\frac{p_{n}}{p_{n+1}}>\sum_{n\geq ...


2

For the first one, suppose $A<\infty.$ Then $p_n/p_{n+1} \to 0.$ By the ratio test, that implies $\sum_{n=1}^{\infty}1/p_n < \infty,$ contradiction.


4

Hint: Bertrand says $p_{n+1}/p_n < 2$.


0

$n^2 + 4n = n (n + 4)$ is the product of two numbers, n and n+4. The product of two integers is composite except when one of them is 0 or 1. n = 1 gives the prime number 1 * (1 + 4) = 5.


1

Since $n^{2} + 4n = n(n+4)$, $n$ and $n+4$ both divide your number. If you assume your number is prime, then $n$ must be $1$ and $n+4$ must be your number. thus the only prime you're looking for is $5$.


2

If $n^2+4n=n(n+4)$ is a prime number then it's divisible by $n$ and $n+4$ but also only 1 and itself. The conclusion is $n=1 , n+4=5 \Rightarrow n^2+4n=5$ and that is a prime number. Only $5$ satisfies this.


1

$p$ must be odd and greater than $3$. Thus $$~~~~~p + 2 \equiv 2 \pm 1 \pmod 3$$ $$\Leftrightarrow p + 4 \equiv 1 \pm 1 \pmod 3$$ If the sign is plus, $p+2 \equiv 3 \equiv 0 \pmod 3$. If the sign is minus, $p+4 \equiv 0 \pmod 3$. In either case, one of these numbers is divisible by $3$, and since they can't be $3$ themselves by assumption, they cannot be ...


4

Following my hint in the comments, one of the numbers $\{n,n+2, n+4\}$ must always be a multiple of $3$. However the hypotheses of the problem are that all three are prime. Hence one of them must be the specific prime $3$, as that is the only prime number that is also a multiple of $3$. So there are three cases: $n=3$. Excluded, since $p>3$ forbids ...


1

This isn't the most clever approach, but it is a universal approach to quadratic diophantine equations to start by removing linear terms (completing the square). $$ \begin{align} p^2+pq+275p+10q &=2008 \end{align} $$ Shift to remove linear terms: $p=u+a,q=v+b$ $$ \begin{align} (u+a)^2+(u+a)(v+b)+275(u+a)+10(v+b) &=2008\\ u^2+uv+(2a+b+275)u+(a+10)v ...


1

Using modular arithmetic like you do is a great way to simplify the problem. While we eliminate the most terms by working modulo 5 as you do, we also eliminate terms working modulo 2, where the equation becomes $$p^2+p+pq\equiv 0 \pmod 2,$$ and since $p^2+p\equiv 0 \pmod 2$, this simplifies further to $pq \equiv 0 \pmod 2$, which tells you that either $p$ ...


1

Because there is alot of solutions, let me present you mine: the equation you stated is equivalent to $$(p+10)(p+q+265)=4658=2\cdot 17\cdot 137$$ and because $p+10>2$ then $p+10\geq 10$ but also $p+q+265\geq 2\cdot 137$ hence $p+2=17$ and $p+q+265=2\cdot 137$ In negative solutions (without (negative) prime assumptions) there is exactly $16$ solutions, ...


1

Suppose that $p>7$. Then $p\ge 11$ so that $p^2+pq+275p+10q\ge 3188$ since $q\ge 2$. Hence $p\le 7$ and we have to check $p=2,3,5,7$. It follows that $(p,q)=(7,2)$.


0

$p^2+pq+275p$ is even. If $p=2$, then $q\not\in\mathbb Z$. Otherwise $p+q+275$ is even. This implies $q=2$. Then $p=7$. So the only solution is $(p,q)=(7,2)$.


0

Indeed, $\log N_{n+1}=\theta(p_{n+1})<p_{n+1}$ doesn't always hold. In particular, here is shown that $\theta(x)-x$ changes sign infinitely often. Since for $p_n<x<p_{n+1}$, $\theta(x)-x=\theta(p_n)-x<\theta(p_n)-p_n$, my inequality fails infinitely many times.


1

An equivalent conjecture: there is some $N$ such that for every large enough $n$, $n\equiv\pm1\pmod k$ for some $6<k<N.$ Now let $\mathcal{P}$ be the set of primes $p$ which are of the form $12m+5$ such that $2m+1$ and $3m+1$ are prime. If $p\in\mathcal{P}$ then $k\ge2m+1$. Hence if $\mathcal{P}$ is infinite (as is believed on standard conjectures, ...


2

If it has a root $\,b^2\equiv a\,$ then $\,0\equiv x^2\!-\!b^2\equiv (x\!-\!b)(x\!+\!b).\,$ Then prime $\,p\mid (x\!-\!b)(x\!+\!b)\,$ so $\,p\mid x\!-\!b\,$ or $\,x\!+\!b,\,$ so $\,x\equiv b\,$ or $\,-b,\,$ and $\,-b\not\equiv b,\,$ else $\, 2b\equiv 0,\,$ contra $\,(p,2)=1=(p,b^2)$ Remark $\ $ More generally a commutative ring $\ne 0$ is an integral domain ...


0

$0 \equiv 5m^2\!+\!m\!+\!4\equiv -2m^2\!+8m\!+\!4 \iff 0\equiv m^2\!-\!4m\!-\!2 \equiv (m\!-\!2)^2+1\iff $ $\!\!\iff (m\!-\!2)^2\equiv -1.\,$ But $\,-1\,$ is not a square: $\,j^2\equiv -1\,\overset{\rm cube}\Rightarrow\, 1\!\!\!\! \underset{\overbrace{\rm Fermat^{\!\!\phantom{1}}}^{\phantom{.}}}\equiv \!\!\! j^6 \equiv (-1)^3\equiv -1$


1

Multiply by the inverse of $5$, which is $3$: $$ 3 \times ( 5 m^2+m+4) \equiv 0 \pmod{7}, $$ which becomes $$ m^2+3m+5 \equiv 0 \pmod{7} $$ Completing the square means finding $a$ and $b$ so the following is true $$ m^2+3m+5 \equiv (m+a)^2+b \pmod{7} $$ Expanding the bracket, $$ 3m+5 \equiv 2am + (a^2+b) \pmod{7} $$ The inverse of $2$ is $4$, so $$ a = 4 ...


2

You're switching “is prime” with “is not prime”. Suppose $n$ is not prime. Then $n$ is divisible by a number $k$ with $1<k<\sqrt{n}<10^3$. But $n$ is not divisible by any number $k$ with $1<k<10^4$. So the assumption $n$ is not prime leads to a contradiction. Hence $n$ is prime. Without prior knowledge that a non prime is divisible by ...


0

Yes. This is rather fundamental, but in general, you only need to test integers less than or equal to the square root of your integer to know if it is prime or not. This is fairly easy to prove, and you can do this by assuming that $n$ is composite and that there exist two unique divisors greater than $\sqrt{n}$. Upon multiplying these two integers, we find ...


1

Occasionally, it is easier to (see how to) prove a stronger assertion than the required assertion. If we try to find a solution of the equation $x^2 + 1 = 4t^2 + 1$ rather than a solution of the congruence $x^2 \equiv -1 \pmod{4t^2+1}$, the solution $x = 2t$ immediately jumps out. Hence a fortiori $(2t)^2 \equiv -1 \pmod{q}$ for every prime factor $q$ of ...



Top 50 recent answers are included