# Tag Info

55

Yes. Consider any prime $p$. (Actually we don't need $p$ to be prime; consider any nonzero number $p$.) You can of course take $F_0 = 0$ which is divisible by $p$, but let's suppose you want some $n > 1$ such that $F_n$ is divisible by $p$. Consider the Fibonacci sequence modulo $p$; call it $F'$. That is, you have $F'_0 = 0$, $F'_1 = 1$, and for $n \ge ... 19 According to the Wikipedia article on Fibonacci numbers if$p$is a prime number then $$F_{p - \left(\frac{p}{5}\right)} \equiv 0 \text{ (mod } p)$$ where$\left(\frac{p}{5}\right)$is the Legendre symbol. $$\left(\frac{p}{5}\right) = \begin{cases} 0 & \textrm{if}\;p =5\\ 1 &\textrm{if}\;p \equiv \pm1 \pmod 5\\ -1 &\textrm{if}\;p \equiv \pm2 ... 16 How do I understand it intuitively? It doesn't really make sense to me that the sum of odd numbers up to 2x+1 should equal x^2 Hope this picture will provide you with the visual aid you need. :-) 7 The trivial answer is: yes F_0=0 is a multiple of any prime (or indeed natural) number. But this can be extended to answer your real question: does this also happen (for given~p) for some F_n with n>0. Indeed, the first coefficient (the one of F_{n-2}, which is 1) of the Fibonacci recurrence is obviously invertible modulo any prime~p, which ... 7 We can in fact show a stronger statement with some algebraic number theory: If p>5 is prime then p|F_{p\pm 1} for some choice of + or -. Suppose \left(\frac{5}{p}\right)=1. In this case, p splits in \mathbf{Z}\left[\frac{1+\sqrt{5}}{2}\right]=\mathbf{Z}[\varphi]. Thus, we can write p=\pm\pi\bar\pi, where \pi and \bar\pi are conjugate ... 6 This is a classical consequence of the Chinese remainder theorem. Denote by p_1,p_2,\ldots,p_r the prime divisors of b. For each i, p_i does not divide both a and N. I claim that there is a x_i\in{\mathbb Z} such that a+Nx_i is not divisible by p_i. Indeed, if p_i divides N then it does not divide a by the above so any x_i will ... 5 Without loss of generality, we may assume |\alpha| < 1. We can construct the desired Taylor series$$ f(x) = \sum_{n=0}^{+\infty} a_n x^n $$as follows. Let f_k(x) be the polynomial$$ f_k(x) = \sum_{n=0}^{k} a_n x^n $$Choose a_0 so that 0 < a_0 < \alpha Choose a_k so that |f_{k-1}(\alpha) + a_k \alpha^k| < \alpha^{k+1} and ... 5 Recall that:$$\sum_{k=0}^{x}k = \frac{x(x+1)}{2}$$Then$$\sum_{k=0}^x(2k + 1) = 2\sum_{k=0}^x k + \sum_{k=0}^x1 = x(x+1) + (x+1) = x^2 + 2x + 1 \neq x^2$$Instead, since x^2 + 2x + 1= (x+1)^2, then$$\sum_{k=0}^x(2k + 1) = (x+1)^2$$Using x-1 in place of x, then you have:$$\sum_{k=0}^{x-1}(2k + 1) = x^2$$5$$k_1a \equiv k_2a \pmod p \iff p \ | \ (k_1 - k_2)a \iff p \ | \ (k_1 - k_2)$$Since in our case k_1, k_2 \in A = \{1, 2, ..., p\} we have that \left| { k_1 - k_2} \right| \lt p and p will not divide (k_1 - k_2) if both elements are from A. So for any two elements r, q \in A \;\; rp \not \equiv qp \pmod p . Which says that every element in ... 5 Borrowing @Jason's notation for:$$S_n(x)=\sum_{i=1}^{n-1}\left(\frac{i}{n}\right)^x$$we have that:$$S_n(x)=-1+(1+1/n)^x\cdot S_{n+1}(x)\leq -1+e^{x/n}\cdot S_{n+1}(x),\tag{1}$$so in order to have S_n(x_n)<1, it is sufficient that S_{n+1}(x_n)<2\cdot e^{-x_n/n}. Now I state, for later proof:$$ ... 4 Using the inequality $$e^{-x/(1-x/k)}\le\left(1-\frac xk\right)^k\le e^{-x}\tag{1}$$ and setting$x=\frac{ik}{n}we get \begin{align} \frac1{n^k}\sum_{i=0}^{n-1}i^k &=\frac1{n^k}\sum_{i=1}^n(n-i)^k\\ &=\sum_{i=1}^n\left(1-\frac in\right)^k\\ &\le\sum_{i=1}^ne^{-ik/n}\\ &\le\frac1{e^{k/n}-1}\tag{2} \end{align} Thus,k=\log(2)n$is an ... 4 I was having some luck by defining $$S_n(x) = \sum_{i=1}^{n-1} \left(\frac{i}{n}\right)^x.$$ In the very least, you get a reasonable justification for the$\log{2}$coefficient. With minimal algebra, one sees $$S_n(x) = \left(\frac{n-1}{n}\right)^x \left[1+S_{n-1}(x)\right].$$ Define$x_n$such that$S_n(x_n)=1$. We write$x_{n}=x_{n-1}+\Delta_n$. So, ... 4 Of course$x=0$works. Can we go lower? If$x$is large and negative, the expression is negative. You will find also that$x=-0.5$works, and you can't go lower, because the expression is then negative. Note, we can write$(x+1)^4-x^4=\left((x+1)^2-x^2)\right)\left((x+1)^2+x^2)\right)=(2x+1)\left((x+1)^2+x^2)\right)$This is$2x+1$times a positive ... 4 Note that we are looking at$(x-1)(x^2+1)$. There are no even solutions. If$x$is odd, then$x^2+1\equiv 2\pmod{4}$. Thus we need$x-1$to be divisible by$2^{n-1}$. For any$n\gt 1$, the solutions modulo$2^n$are$1$and$1+2^{n-1}$. Remark: Lifting will also work. But the polynomial is so nakedly factorable that I doubt this was intended to be an ... 4 Hint: We have$p-1\equiv -1\equiv (p-1)!=(p-3)!(p-1)(p-2)\equiv (p-3)!(-1)(-2)\equiv 2(p-3)!\pmod{p}$. Remark: Your proof begins in the right way, Wilson's Theorem is the correct tool. After that there are problems. We are trying to get information about$(p-3)!$, but it does not appear explicitly in the rest of the calculation. 3 For a more general approach, let$\alpha$be any algebraic number; suppose that$\alpha$has minimal polynomial$p(x)$and you want to evaluate$1/f(\alpha)$, where$f$is a polynomial which is not a multiple of$p$. (If$f$is a multiple of$p$then$f(\alpha)=0$and so$1/f(\alpha)$makes no sense.) Use the Euclidean algorithm for polynomials to divide ... 3 We prove this via induction. Base case ($x = 1$): $$1^2 = \sum_{k=0}^{1-1} (2k+1) = \sum_{k=0}^0 (2k+1) = 2\cdot 0+1 = 1$$ Inductive step: Suppose it is true for some$x$. Now, we note that $$(x+1)^2 = x^2 + 2x + 1$$ and that $$\sum_{k=0}^{x+1-1} (2k+1) = \sum_{k=0}^{x-1} (2k+1) + 2x+1$$ 3 A number is divisible by$ 8 $if the last three digits are divisible by$ 8$. Now, we can arrange the first$5$digits of our answer in$ 5^5 $ways, because each of the position can take$ 1$of$5$values. Now, our problem reduces to the following. How many three digit numbers formed with$\{1,2,3,4,5\}$are divisible by$8$? We can enumerate all the ... 3 Standard answer: there are proofs of statements of this type: for large enough real numbers$x,$there is a prime between$x$and$x + x^{21/40};$the important part is that$21/40$is bigger than$1/2.$Here, as in all such results, nobody knows how big "large enough" needs to be. Such results are collectively called "ineffective," as they cannot be used to ... 3 Note that the maximum power of$2$which divides$n!$is $$k=\sum_{r=1}^{\infty}\lfloor\frac {n!}{2^r}\rfloor$$ The sum is finite (later terms are zero), so for$34!$we have$k=17+8+4+2+1=32$so that$34!$is the first factorial divisible by$2^{32}$. NB To see that it is the first, note that$34$carries a factor of$2$, which gets us over the mark. 3 Let$S = \sum_{i=1}^{q-1} \{ \frac{ip}{q} \}$. Since$p$and$q$are relatively prime, multiplication by$p$permutes the nonzero residues mod$q$, and so $$S = \sum_{i=1}^{q-1} \{ \frac{ip}{q} \} = \sum_{i=1}^{q-1} \{ \frac{i}{q} \} = \frac 1q \sum_{i=1}^{q-1} i = \frac 1q \cdot \frac{q(q-1)}{2} = \frac{q-1}{2} .$$ 2 Of all the numbers that are formed with 1,2,3,4,5 - the last three digits need to be divisible by 8. There are 5^3 ways you could arrange the five numbers for the last three digits. Of these last three digits that are divisible by 8 are 312, 152, 512, 432, 352, 112, 232, 224, 144, 424, 344, 552, 544. A total of 13 of them which I got by brute force ... 2 An example for Hasse-Minkowski might be worth studying it, i.e., the binary quadratic form$5x^2 + 7y^2 − 13z^2$has a non-trivial rational root since it has a$p$-adic one for every prime, and obviously also a real root. Another example is the$3$-square theorem of Gauss: A positive integer$n$is the sum of three squares if and only if$-n$is not a ... 2 My personal elementary favorites are: Prove that $$\frac11+\frac12+\frac13+\cdots+\frac1n$$ is not an integer, if$n>1$. And the variant of proving that $$\frac11+\frac13+\frac15+\cdots+\frac1{2n+1}$$ is not an integer, if$n\ge1$. Both are resolved by using the non-archimedean$p$-adic triangle inequality for a suitable choice of$p. 2 They're called truncatable primes. For a list of them on OEIS, see A024785, A020994, A055521 2 Notice : \begin{align}(x + 1)^2 - x^2 &= x^2 + 2x + 1 - x^2 \\&= 2x + 1\end{align} We take a summation on both sides and see that a lot of cancellation occurs on the LHS: $$\sum_{k = 0}^{x-1}\left((x+1)^2 - x^2\right) = \sum_{k = 0}^{x-1}(2x+1)\\ (x -1 + 1)^2 - 0^2 = \sum_{k = 0}^{x-1}(2x+1\\ x^2 = \sum_{k = 0}^{x-1}(2x+1)$$ 2x = 0$is one such integer, because in that case$(x+1)^4 - x^4 = 1^4 - 0^4 = 1$, and its fourth root is$1$which is again an integer. No smaller integer$x$is possible, because for the fourth root of$f(x) = (x+1)^4 - x^4$to exist,$f(x)$must be nonnegative, and the smallest possible nonnegative value$0$is not possible (that would require$(x+1)^4 = ...

2

If we write $x = k+h$ with $0 \leqslant h < 1$, then we have $$\left\lvert \ln \frac{\lfloor x\rfloor}{x}\right\rvert = \ln \frac{k+h}{k} = \ln \left(1+\frac{h}{k}\right) \leqslant \frac{h}{k} < \frac{1}{k} = \frac{1}{\lfloor x\rfloor}.$$ In the second, we have \ln x = \ln \left(\lfloor x\rfloor \frac{x}{\lfloor x\rfloor}\right) = \ln \lfloor ...

2

Since the indices of the factors in the strictly increasing order don't actually play any role, I'll use $A,B,P,Q$ to denote the actual factors instead of $\tau_a(n)$, $\tau_b(n)$, $\tau_p(n)$ and $\tau_q(n)$. The condition given can then be rewritten as $AB=PQ=n$ and $A+B=P-Q$. Let's start by showing that all numbers from OEIS A009112 admit such ...

2

If $s$ is a nontrivial zero of $\zeta$ off the critical line then the four numbers $\{s,\bar{s},1-s,1-\bar{s}\}$ would all be nontrivial zeros off the line. Note $1-\bar{s}$ is the image of $s$ across the critical line, so they are close together, but $\bar{s}$ is the image of $s$ across the real axis, which won't look close to $s$. Your image even depicts ...

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