# Tag Info

16

If $n$ is not prime, then at least one of the factors of $n$ is at most as large as $\sqrt n$. To see why, let's suppose not. Since $n$ is not prime, $n = ab$ for some $a,b \neq 1$. If both $a$ and $b$ are larger than $\sqrt n$, then $a\cdot b > \sqrt n \cdot \sqrt n = n$. This clearly cannot be! So you only need to check for factors up to $\sqrt n$.

11

$$15x^2+19x\equiv 5 \mod 11$$ is equivalent to $$15x^2+19x +6 \equiv 0 \mod 11$$ by the fact that we can subtract $5$ from both sides of the congruence (and $-5\equiv 6 \mod 11$). From here, we factor $15x^2+19x+6$ to give $(3x+2)(5x+3)$. This means that our original quadratic congruence is equivalent to $$(3x+2)(5x+3)\equiv 0 \mod 11.$$ This will ...

10

Write your equation as $m^2 - m = n^5 - n$. You want $m = (1 + \sqrt{4 n^5 - 4 n + 1})/2$ to be an integer. Trying the first $10^6$ values of $n$, we find that $4n^5 - 4n + 1$ is a square for $n = 1, 2, 3, 30$, corresponding to $m = 1, 6, 16, 4930$. The curve $x^2 - x - y^5 + y$ has genus $2$ (according to Maple), so by Faltings's theorem there are only ...

9

John, in cyclotomic extensions of $\mathbf Q$ the Galois group acts like a power map only on the roots of unity, not on general elements, so don't think about the Galois group as "exponential." For comparison, complex conjugation is an element of ${\rm Gal}(\mathbf C/\mathbf R)$ and it acts on $i$ by sending it to $-i$, but that doesn't mean the Galois ...

8

Choose any positive integer $a > n$ such that $\gcd(a,n)=1$ Since $d|n \implies \gcd(a,d)=\gcd(a,n)=1$ By Euler's Theorem, $a^{\phi (n)} \equiv 1 \pmod n$ $\implies n|(a^{\phi (n)}-1)$ $\implies d|(a^{\phi (n)}-1)$ $\implies a^{\phi (n)} \equiv 1 \pmod d$ Again, by Euler's Theorem, since $\gcd(a,d)=1$, $a^{\phi (d)} ... 7 I'd say you're on a good track, but more should be said. As you noted the sum of all elements of$A$is$55$. You should argue (using the$55$fact) that for any subset$B$of$A$, exactly one of$B$and$B^c$(complement of$B$) have a sum greater than or equal to$28$. Then pairing up subsets of$A$by complements, we see that exactly half the subsets ... 6 HINT: I expect that you know that a number is rational if and only if its decimal expansion is eventually periodic. Suppose that the expansion eventually repeats with period$p$. Show that there are two consecutive powers of$2$whose after the initial aperiodic segment whose lengths (when written in the usual way in base ten) are the same multiple of$p$. ... 6 Assume$x=3^{100} a$to balance all those large powers of 3: $$y^7 = 2\cdot 3^{700} \left( 7a^6 + 35a^4 + 21a^2 + 1 \right)$$ Due to the common factor,$y$should be of the form$y=2\cdot 3^{100} b: \begin{align} 64 b^7 &= 7a^6 + 35a^4 + 21a^2 + 1 \\ &= \sum_{k=0}^3 \binom7{2k} a^{2k} \\ &= \frac{(1+a)^7 + (1-a)^7}2 \\ (2b)^7 &= (1+a)^7 ... 5 Using the characterisation of these triples, it suffices to show that any such number can be written asm^2-n^2$,$2mn$or$m^2+n^2$with some numbers$m>n$. The case$m^2-n^2$covers "the most" numbers (only those$\equiv 2 \mod 4$remain), the rest is covered by$2mn$. 5 Oftentimes in mathematics we find that by expanding our universe we can find out more about a subject that has its roots in something simpler. Look at polynomials over the real numbers, some of them don't have roots, but all of them have roots in$\Bbb C$, the complex numbers. Quadratic fields grew out of the early study of quadratic forms in two variables, ... 5 Since$\sigma(n)>0$we have$d<2N$, together with$(2/3)N^2<d$we get$(2/3)N^2<2N$which is verified only for$0< N< 3$, which leaves only 2 cases to be checked, namely$1$and$2$. edit:After the question being asked has been changed the first part of my answer is irrelevant. I can't completely answer the new question, but I can show ... 5$(1+\sqrt{71})^{71} + (\sqrt{71}-1)^{71}$is not an integer. However, if you meant$(1+\sqrt{71})^{71} + (1-\sqrt{71})^{71}$, then it is indeed an integer. If$x_n = (1+\sqrt{71})^n + (1-\sqrt{71})^n$, we then have$x_n$to satisfy the recurrence $$x_{n+1} = 2x_n + 70x_{n-1}$$ where$x_0 = 2$and$x_1=2$. Hence, we see that $$x_{n+1} = 2x_n \pmod{10}$$ ... 4 I think you refer to a theorem of Kummer: Fermat's Last Theorem is true for an odd prime$p$if and only if$p$doe not divide the class number of the cyclotomic extension$\mathbf Q(\zeta_p)$, i. e. the order the the group of fractionary ideals of this field modulo principal ideals. Such a prime number is called a regular prime. Kummer criterion: An odd ... 4 I'm not sure which level to write this at. Here is a completely elementary proof: As you say, if$p \equiv 1$,$3$,$7$or$9 \bmod 20$, then$\left( \frac{-5}{p} \right) = 1$. Let$p$be in one of these residue classes and let$a$be a square root of$-5$modulo$p$. Let$\Lambda \subset \mathbb{Z}^2$be the lattice of pairs$(x,y)$such that$x \equiv ay ...

4

HINT Note that $m^3 \equiv 0, \pm1 \pmod9$.

4

Here's how I would start (don't know if I will finish): If $m^2-n^5 = m - n$, then $m^2-m = n^5-n$ or $m(m-1) =n(n^4-1) =n(n^2-1)(n^2+1) =n(n-1)(n+1)(n^2+1)$. The RHS needs to factor into two terms that differ by $1$. This seems important, but I don't know how to make use of this. Also, multiplying by 4 and adding $1$ (to make the left side a square), ...

4

Note that if $n$ is composite, then $n$ has a non-trivial factor $i$ such that $i \le \sqrt{n}$. Otherwise, any nontrivial factorization $n = ab$ would force $a, b > \sqrt{n}$, so that $n = ab > \sqrt{n}\times \sqrt{n} = n$, a contradiction.

4

Hint: What does 'primitive' mean? So the statement we are trying to prove here is if $(x,y,z)$ is a primitive Pytagorian triple, that is to say $hcf(x,y,z)=1$ and $x^2+y^2=z^2$, then $5$ divides at most one of them. If 5 divides all three of them then 5 divides the highest common factor of $x,y$ and $z$ and this is a contradiction. So suppose 5 divides ...

3

The proof is by infinite descent. Let $n,a,b,c$ be the smallest possible solution to $W(n,a,b,c) = 0$, where $n>3$. Since he is almost sure that there exists a polynomial, discoverable by computer, with positive coefficients such that: $$W(n,a,b,c) = P\left(W(n,a-1,b,c), W(n,a,b-1,c), \ldots W(n -1,a,b,c), \ldots\right)$$ for $n>3$. This would mean ...

3

Kummer's Theorem, a proof of which is given in this answer, in the case $p=2$ says If, when you add $m$ and $n$ in binary, there are no carries, then $\binom{m+n}{n}$ will be odd. Thus, the largest $n\le m$, will be the binary ones'-complement of $m$ (truncated to the size of $m$). For example, if $m=5=101_{\text{two}}$, then $n=10_{\text{two}}=2$. ...

3

Roth's Theorem will give you an upper bound: http://wiki.math.toronto.edu/TorontoMathWiki/images/2/2d/Expo_paper.pdf In that paper it is Theorem 1.3 (bottom of first page). It says: Theorem (Roth, 1953) For any $\delta>0$ if $k>\exp(\exp(c\delta^{-1}))$ (for some absolute constant $c>0$) and $A\subseteq \{1, 2, 3, ..., k\}$ and $|A|\geq \delta k$ ...

3

As for an upper bound, we get into work related to Erdos' conjecture on arithmetic progressions (which has not been proven even in the case of arithmetic progression of length 3). I believe the strongest known result is Sander's proof that, if $f(k)$ is the size of the largest subset of a $k$-element progression free from arithmetic progression of length ...

3

[Edit: I didn't read the post properly, so this answers a quite different though related question: what is the count of $(n_1,n_2)$ such that $n_1^2+n^2 \leq N$. Gerry Myerson's response answers the question that was actually asked.] This is a nice question that was first studied thoroughly by Gauss and goes by the name 'Gauss's circle problem.' We know ...

3

$$6 \equiv -1 \pmod{7}$$ .....

3

Assume you have the Pythagorean relation $u^2 + v^2 = c^2$ Then \begin{align} (u^2 + v^2) + (u^2 + v^2) & = 2c^2\\ (u^2 + v^2 + 2uv) + (u^2 + v^2 - 2uv) & = 2c^2\\ (u + v)^2 + (u - v)^2 & = 2c^2\\ \end{align} Thus if $a = u + v$ and $b = |u - v|$ $a^2 + b^2 = 2c^2$

3

HINT: Induction is much easier, but if you really must use Binet’s formula, note that your summations are geometric, with ratios $\alpha^2$ and $\beta^2$, respectively; you can use the familiar formula for the sum of a finite geometric series. You also know that $\alpha$ and $\beta$ satisfy the equation $x^2-x-1=0$, so $\alpha^2-1=\alpha$ and ...

3

We have $$\sum_{n\le x}\tau(n)\sim \sum_{n\le x}\log(n),$$ so that the average value of $\tau(n)$ is indeed $\log(n)$, but from Hardy and Ramanujan we know, since $2^{\omega(n)}\le \tau(n)\le 2­^{\Omega(n)}$, that for most numbers $n$, $$\tau(n)=\log(n)^{\log(2)+o(1)},$$ where $\log (2)$ is around $0.693$. The normal value of $\omega (n)$ resp. ...

3

Given $x_1,x_2,\ldots,x_7$, set $x_i = \tan(t_i)$, where $t_i \in \left(-\dfrac{\pi}2, \dfrac{\pi}2\right)$. Divide $\left(-\dfrac{\pi}2, \dfrac{\pi}2\right)$ into $6$ equal intervals of length $\dfrac{\pi}6$. By PHP, we have two of the $t_i$'s to lie in the same interval, i.e., we have $$-\dfrac{\pi}6 < t_i - t_j < \dfrac{\pi}6$$ Now taking $\tan$ on ...

3

No induction necessary. The equation $x^2 -10x +22 = 0$ has the roots $5-\sqrt 3$ and $5+\sqrt 3$. We know that this function is positive outside the roots, which means on $(-\infty, 5-\sqrt 3) \cup (5+\sqrt 3, \infty)$. The first interval contains the natural numbers $0,1,2,3$, while the second one all the natural numbers starting from $7$ (use that \$\sqrt ...

3

A number is rational if and only if it has an eventually repeating decimal expansion. So you should show that this decimal expansion does not have an eventually repeating expansion.

Only top voted, non community-wiki answers of a minimum length are eligible