Tag Info

New answers tagged

0

Use Pascal's identity and Wilson's theorem: $${n-1\choose k}+{n-1\choose k-1}={n\choose k}$$ Since ${p\choose k}\equiv 0\mod p$ when $1\le k\le p-1$, the result follows.


0

HINT: use Pascal's rule and Strong induction


0

This is a variation on Fermat's theorem. The number of solutions is nite. Will write a more General equation: $$(x+r)(y+r)(z+a)=3xyz$$ If $z,a$ - Will ask themselves. Then the solution can be written; $$r=ps(2z-a)$$ $$x=((p+3s)z+ap)s$$ $$y=(z+a)(p+s)p$$ $$***$$ $$x=((z+a)p+s)s$$ $$y=(z+a)(3zp+s)p$$ $p,s$ - integers asked us. You must consider ...


1

Notice $T(2,k+c)=T((T(2,c),k)$. So $T(2,k+c)>(2010,c)$ if and only if $T(2,c)>2010$. So let's compute some values of $T(2,c)$: $T(2,1)=2$ $T(2,2)=2^2=4$ $T(2,3)=2^4=16$ $T(2,4)=2^{16}=65536$. So $c=4$.


0

Let $x=(\overline{x_k}), y=(\overline{y_k}) \in \mathbb{Z}_p \setminus \{0\}$. Since $x \neq 0, y \neq 0,$ there exists $n, m \in \mathbb{N}$ such that $x_n \neq 0$ in $\mathbb{Z}/p^{n+1}\mathbb{Z}$ and $y_m \neq 0$ in $\mathbb{Z}/p^{m+1}\mathbb{Z}$ (Choose the smallest integers $m, n$ with the that property). Let $l := m + n + 1.$ Then $x_l = x_n$ in ...


0

Let's look at the definition of $\mathbb{Z}_p:$ $$ \mathbb{Z}_p := \{(x_n)_{n \geq 0} \in \Pi_{n \in \mathbb{N}_0}\mathbb{Z}/p^{n+1}\mathbb{Z} | x_n = \eta_{mn}(x_m), \forall m \geq n \} $$ where for $m \geq n, \eta_{mn}: \mathbb{Z}/p^{m}\mathbb{Z} \rightarrow \mathbb{Z}/p^{n}\mathbb{Z}$ is the natural map induced by the inclusion $p^m\mathbb{Z} \subseteq ...


0

Let's look at the definition of $\mathbb{Z}_p:$ $$ \mathbb{Z}_p := \{(x_n)_{n \geq 0} \in \Pi_{n \in \mathbb{N}_0}\mathbb{Z}/p^{n+1}\mathbb{Z} | x_n = \eta_{mn}(x_m), \forall m \geq n \} $$ where for $m \geq n, \eta_{mn}: \mathbb{Z}/p^{m}\mathbb{Z} \rightarrow \mathbb{Z}/p^{n}\mathbb{Z}$ is the natural map induced by the inclusion $p^m\mathbb{Z} \subseteq ...


1

The question asks for any such integer, so note that $2\cdot13-5\cdot5=1$, now $13$ divides $1+5\cdot5$ and $5$ divides $1-2\cdot3$, so $$4(1+5\cdot5)+7(1-2\cdot13)=4\cdot26-7\cdot25=-71$$ is an example of such integer.


1

Note that $13\times 2=26\equiv 1 \mod 5$ and $5\times 8=40\equiv 1 \mod 13$ So that $26x+40y \equiv x \mod 5; \equiv y \mod 13$ so we can put $x=4, y=7$ to obtain $104+280=384$ as one solution. We can obtain other solutions by adjusting by a multiple of $65$ - $390$ is obvious giving $-6$ and then $59$ by adding $65$. The merit of this method, which ...


1

Hint: Use inspection :   $5x = 13 y + 3 \\ 13(1) + 3 = 16 \\ 13(2) + 3 = 29 \\ 13(3) + 3 = 42 \\ 13(4) + 3 = 5(11) \quad\checkmark \\ \therefore \forall k\in\mathbb Z: 5 (11+13k) = 13(4+5k) +3 \\[2ex] {\forall k\in\Bbb Z, \exists n\in\Bbb Z: \underline{\quad n = 59 + 65 k\quad}} $


4

${\bf Brute\ force}:\ \ 5\,\Bbb Z+\color{green}4 = \{\ldots, \color{#c00}{-6},-1,\color{green}4,9,13,\ldots\}$ $\qquad\qquad\qquad\ \ 13\Bbb Z+\color{orange}7 = \{\ldots, \color{#c00}{-6},\color{orange}7,20,\ldots\}\,\ $ so $\,\ n\equiv \color{#c00}{-6}\pmod{65 = \rm{lcm}(5,13)}\ $ $\bf Algorithmically,$ using CRT $\quad\,\ {\rm mod}\ 5\!:\,\ n \equiv ...


1

$5x - 13y = 7-4 = 3 \Rightarrow 5x = 15y + 3 - 2y \Rightarrow x = 3y + \dfrac{3-2y}{5} \Rightarrow 5\mid 3-2y \Rightarrow 3-2y = 5k \Rightarrow y = \dfrac{3-5k}{2} = \dfrac{3-k}{2} - 2k \Rightarrow 2\mid 3-k \Rightarrow 3-k = 2h \Rightarrow k = 3-2h \Rightarrow 3 - 5k = 3 - 5(3-2h) = -12 + 10h \Rightarrow y = \dfrac{3-5k}{2} = \dfrac{-12+10h}{2} = 5h-6 ...


1

From $$\phi^x - \cos(x\pi)\phi^{-x} = 11261957\sqrt{5}$$ we can assume that $\phi^{-x}$ is small and get $$\phi^x \approx 11261957\sqrt{5}$$ The solution to this is $$x \approx \frac{ln(11261957\sqrt{5})}{ln(\phi)} \approx 35.414$$ and indeed the $35^\text{th}$ and $36^\text{th}$ Fibonacci numbers are $$9227465 \qquad \text{and} \qquad 14930352$$ which are ...


1

maybe you can see it the following way: you are looking for a $\beta >0$ and rational such that $(p+\beta)^2 < 2$, note that this means that necessarily $p+\beta < 2^{\frac{1}{2}}<2$ . Now $(p+\beta)^2 < 2 \Leftrightarrow 2\beta p + \beta^2 < 2-p^2 \Leftrightarrow \beta< \frac{2-p^2}{p + p +\beta} $ but for any $\beta$ you are looking ...


0

EDIT: note that your binary quadratic form $x^2 + y^2$ has discriminant $\Delta = -4.$ Somewhere you need to find a proof of the fact that, for prime $q \equiv 3 \pmod 4,$ we always have $$ (-1|q) = -1. $$ For instance, Niven and Zuckerman (and Montgomery) page 132, Theorem 3.1 part (5), says $$ (-1|p) = (-1)^{(p-1)/2}. $$ Same thing in Ireland and Rosen, ...


1

You can calculate it recursively given the formula $$F_n=F_{n-2}+F_{n-1}$$(you can use a code which does it). Formulas which are iterative like $$(\omega=\frac{1+\sqrt 5}{2})\quad F_n=\frac{\omega^{n+1}-\bar\omega^{n+1}}{\sqrt 5}$$ are not that useful in your case, since that's equivalent to solve an equation which for big values of $F_n$ is not that easy to ...


1

Observe that: $p^2 < 2 \Rightarrow p^2+2p < 2 + 2p \Rightarrow p(p+2) < 2+2p \Rightarrow p < \dfrac{2+2p}{p+2}\in \mathbb{Q}$. He then set $q = \dfrac{2+2p}{p+2}$, then $p < q$ from definition of $q$, and furthermore: $q^2 - 2 = \left(\dfrac{2+2p}{p+2}\right)^2 - 2= \dfrac{4+8p+4p^2}{p^2+4p+4} - 2= \dfrac{2}{(p+2)^2}\cdot (p^2-2) < ...


2

He is defining $q$ by the formula above. Because $p^2-2<0$, we have $q>p$ and because of the formula for $q^2-2$ (which is $<0$), we have $q^2 < 2$. So $q \in A $ and $p<q$.


3

There are no natural solutions for $x$ and $y$. A quick bit of important information: If $C_n$ is the $n$th non-negative cube ($0,1,8,...$), then $C_{n+1}-C_n = 3n^2+3n+1$. (This can be grasped visually by a similar method to the visual proof that the consecutive differences of consecutive squares are consecutive odd integers.) Let $s,a$ be positive ...


1

For each prime $p$, let $\nu_p(x)$ denote the largest power of $p$ that divides $x$. Note that for any $x,y$, we have that $\nu_p(xy)=\nu_p(x)+\nu_p(y)$. Saying that $x$ and $y$ are relatively prime means that for each prime $p$, $\nu_p(xy)$ is either $0$ or one of $\nu_p(x)$, $\nu_p(y)$, indeed: for example, if $p$ divides $x$, then it cannot divide $y$, so ...


4

Your proof does not suffice. At the end, your conclusion that if a prime $p|xy$, then $p^2|x$ or $p^2|y$ is correct, but it doesn't exclude, for instance, that $p^3|y$ but $p^4\not| y$, in which case $y$ wouldn't be square. However, you're going in the right direction. Notice that we can write $$x=p_1p_2p_3\ldots p_i$$ for some primes $p_i$ and ...


7

This hinges on the fact that $$\sum_{p\text{ prime}}\frac1p=+\infty$$ which in turn implies that $$\prod_{p\text{ prime}}\frac{p-1}p=0\,.$$ Once you know this fact, the proof is easy. Let $p_n$ be the $n$-th prime. Let $\epsilon>0$. There is some prime number $q=p_{N}$ such that $\frac{q-1}{q}\geq 1-\epsilon$. Then consider the sequence of numbers ...


0

The issue here is that you need to define what a 'number' actually is. According to wikipedia - not the best of sources, but should be enough here -'A number is a mathematical object used to count, measure, and label'. Basically, all you need to have some kind of 'numbers' is a set where you have defined operations, giving you - depending on the exact ...


0

A good thing to note is that if you have a polynomial with all of its coefficients in $\mathbb C$, then all roots of this polynomial lie in $\mathbb C$. This does not hold for something like $\mathbb R$ or even $\mathbb Z$ (see $x^2 + 1$). This explains why complex numbers are so important. Now on the other hand, you may ask why not use quaternions, ...


0

The term number really doesn't make too much sense and exists mostly for historical reasons (imo). It vaguely describes some element of some algebraic structure, so we can't really speak of an 'ultimate' set of numbers. But since you are looking for something 'bigger': Consider quarternions, hyperreals, ordinals, surreals and surcomplex numbers (use ...


1

From what I've read you can keep going with quaternions and octonions. http://en.wikipedia.org/wiki/Octonion I'd imagine if you wanted to you could make a 16-tuple equivalent, and keep going, but I don't think there's much use for them or they would have a name.


1

There is a good Wikipedia page on the subject. I'll restrict my answer to concern the positive integers. The zeta function: $$ \zeta: \mathbb{N} \rightarrow \mathbb{R}: s \mapsto \sum_{n=1}^{\infty} \frac{1}{n^s} $$ can be evaluated at even integers to give some surprising results. The case of $n = 2$ is known as the basel problem, which was a famous ...


1

Your second question was how to solve the equation $x^2-1\equiv0\pmod{125}$. Because $125=5^3$, and $5$ is prime, $(x-1)$ and $(x+1)$ should in total have at least three factors $5$. Because $\gcd(x-1,x+1)\leq2$, it cannot happen that both $x-1$ and $x+1$ are divisible by $5$, so it follows that either $125\vert x+1$ and $5\nmid x-1$ or $125\vert x-1$ and ...


1

Here's a useful theorem: Lagrange's Theorem: If $f$ is a polynomial of degree $n$ and $p$ is prime, then the equation $$f(x) \equiv 0 \pmod p$$has at most $n$ solutions. Note that if $f(x) \equiv 0 \pmod {p^k}$, then certainly $f(x) \equiv 0 \pmod {p^j}$ for any $j \le k$. This allows us to significantly reduce what we have to check. For example, by ...


0

${\mathbb Z}_n$ is a monoid (a semigroup with 1) under multiplication. 0 is its absorbing element. Absorbing element can’t be invertible unless the monoid is trivial (1 = 0); that’s why for $n>1$ there is no group.


1

Hint: $x^2 - y^2 = (x+y)(x-y)$. $x+y$ and $x-y$ can be any integers that are either both odd or both even. So the only positive integers that can't be written in this way are ...


5

You can't prove this because it's not true. Consider $$\{6,10,15\}$$ The $\gcd$ of all of them is $1$, but there is no pair whose $\gcd$ is $1$.


2

Yes, there is such a function and it has been studied for at least a century. See Sloane's A002375. But it doesn't have a set letter specified for it. Here I will use $g$. So, for example, $g(36) = 4$, $g(38) = 2$. (If you're looking in Sloane's, be sure to divide by 2 before looking up). There is also a function which requires the primes to be distinct, so ...


2

Brun's theorem follows from the bound $$ \pi_2(x) = O\left(\frac{x(\log\log x)^2}{(\log x)^2}\right), $$ where $\pi_2(x)$ is the number of twin primes less than $x$. On the other hand, the existence of twin primes between each $n$ and $2n$ only implies $\pi_2(x) = \Omega(\log x)$ (as Myself notes in the comments), so there is no contradiction. Moreover, it ...


1

The idea is essentially the same as in the binomial case: To expand $$(X_1 + \cdots + X_m)^n,$$ one determines the possible products of the $X_i$ that can occur, namely all of the terms $$X_1^{k_1} \cdots X_m^{k_m}$$ with total degree $k_1 + \cdots + k_m = n$ in the monomials, and the Multinomial Theorem tells you that the coefficients of those terms are ...


1

Here is a link for a beautiful paper by Eisenbud, Harris, and Green: Eisenbud, David; Green, Mark; Harris, Joe: Cayley-Bacharach theorems and conjectures. Bull. Amer. Math. Soc. (N.S.) 33 (1996), no. 3, 295–324. See Theorem CB1, Theorem CB2, and Theorem CB3. The question you asked is actually Theorem CB2.


1

See Chapter 1 of Cox. Primes of the form $x^2+ny^2$ and Chapter 1 of Lemmermeyer. Reciprocity Laws: From Euler to Eisenstein for some info and further references.


3

The determinant of $T$, when nonzero, has to be an integer for $T$ to maintain integrality of vectors (proof: a simplex with integer vertices and minimal volume has to map to a finite union of such). This rules out odd $n$. Computation of the determinant can be accomplished using the formula for eigenvalues of circulant matrices, here $(1+\omega)/2$ with ...


33

No, because if $x=\frac{a}{b}$, $y=\frac{c}{d}$, and $z=\frac{e}{f}$ were rational solutions, so that $$\left(\frac{a}{b}\right)^3+\left(\frac{c}{d}\right)^3=\left(\frac{e}{f}\right)^3,$$ then there would be an integer solution $$(adf)^3+(bcf)^3=(bde)^3$$ (edit: this is just writing out the details of Did's answer)


52

No--multiplying any rational solution by the product of their denominators, say, would yield an integer solution.


5

Rewrite the original equation $3m^2+m=4n^2+n$ as $$12m^2+12n^2+m-n-24mn=16n^2+9m^2-24mn.$$ This factors as $$(m-n)(12(m-n)+1)=(4n-3m)^2.$$ Since $\gcd(m-n,12(m-n)+1)=1$, it follows that $m-n$ is a perfect square, as desired.


1

It became interesting for the General case. When the difference is a square? Write so equation: $$aX^2+X=bY^2+Y$$ If you use the solutions of the Pell equation. $$p^2-abs^2=\pm1$$ Then decisions can be recorded. $$X=\pm(p+bs)s$$ $$Y=\pm(p+as)s$$ $p,s$ - can be of any sign. So the difference will be equal. $$X-Y=\pm(b-a)s^2$$ Mean difference ...


3

The smallest number with at least $500$ divisors is $2^6\times 3^2 \times 5^2 \times 7 \times 11 \times 13 = 14414400$ The smallest number with at exactly $500$ divisors is $2^4\times 3^4 \times 5^4 \times 7 \times 11 = 62370000$ The smallest number with at exactly $500$ divisors apart from itself is $2^{166}\times 3^2 = ...


3

To get you started Assume that the largest number that is divisible by 500 different numbers is $n$, then assume $n$ is not divisible by $2$. and is instead divisible by $x$, which is the smallest positive integer than $n$ can be divided by, hence $x$ must be larger than 2. To finish the proof (so do not read if you just want to get started) we find that ...


0

The short answer to the question is "no". For each of $$ n \in \{ 11, 35, 133, 259, 2200 \}, $$ we can find distinct primes $p$ and $q$ for which we have $$ p^a+q^b=p^c+q^d = n $$ with $(a,b) \neq (c,d)$ and all of $a, b, c$ and $d$ positive integers. Probably this property is not true for other values of $n$, but that does not appear at all easy to prove. ...


4

The elimination in Lab's answer essentially employs the extended Euclidean algorithm to compute a Bezout identity. As usual, when we need only the result, such calculations can be simplified using modular arithmetic (so simple they can often be done mentally with practice). For example $$\begin{eqnarray} {\rm mod}\,\ \color{#0c0}{2n^2}\!+\color{#c00}1\!:\ \ ...


3

Let $n$ be the smallest positive number that has $k>1$ divisors and let $n=p_1^{r_1}\times\cdots\times p_s^{r_s}$ be its factorization in primes. If $n$ is odd then $2<p_i$ for $i=1,\dots,s$. Replacing one of the $p_i$ by $2$ results in a smaller number that has the same number of divisors ($k=r_1\times\cdots\times r_s$) so a contradiction is found.


4

HINT: If integer $d$ divides $n^3+9n-17,2n^2+1$ $d$ must divide $2(n^3+9n-17)-n(2n^2+1)=17n-34$ $d$ must divide $17(2n^2+1)-2n(17n-34)=68n+17$ $d$ must divide $68n+17-4(17n-34)=153$ So the necessary condition is $2n^2+1$ must divide $153$ $\implies2n^2+1\le153\iff n^2\le76\iff-9<n<9$


20

If $n$ is odd, let $p$ be its smallest prime divisor, and $p^r$ the greatest power of $p$ that divides $n$. Then, the number $$\frac{2^rn}{p^r}$$ has the same number of divisors, it is smaller than $n$ and it is even.


19

Hint: Try to construct the smallest number with $k>1$ divisors. If it does not have $2$ as a divisor, can it be the smallest?



Top 50 recent answers are included