# Tag Info

## Hot answers tagged divisibility

23

$56$ and $65$ are relatively prime, so if $56x=65y$, then $65\mid x$ and $56\mid y$; say $x=65m$ and $y=56n$. Then $$56\cdot65m=56x=65y=65\cdot56n\;,$$ so $m=n$. Thus, the solutions are of the form $x=65k,y=56k$ for integers $k$, and $$x+y=(65+56)k=121k=11(11k)\;.$$ Thus, $x+y$ is even divisible by $11^2$.

9

Assume that there exists a natural number $n$ such that $4\nmid (5^n-1)$. Let $n$ be smallest such number (i.e. $n=\min\{m|4\nmid (5^m-1)\}$ and since every non-empety subset of natural numbers contains a minimal element, $n$ is well defined). Since $4|5^1-1=4$, we have $n>1$. So, by our definition, $4|(5^{n-1}-1)$, but then $4|(5(5^{n-1}-1)+4)=5^n-1$ - a ...

9

\begin{align} \frac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} &=\frac{\displaystyle\left(\sum_{i=1}^{n-1}a_i\right)!}{\displaystyle\prod_{i=1}^{n-1}a_i!} \frac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\left(\sum_{i=1}^{n-1}a_i\right)!\ a_n!}\\ ... 7 Hints: If you know group theory, this follows from Lagrange's theorem applied to S_{n!} and a suitable subgroup of it. Otherwise note that for any prime p and for any positive integer m, the highest power of p dividing m! is \displaystyle\sum_{i = 1}^\infty \lfloor m/p^i\rfloor $$and for any positive integer k and real number x, ... 5 You have a very valuable hypothesis that f\in\Bbb Z[x]: the coefficients are integers (if this were not given you could only prove them to be rational). This allows reducing the polynomial itself modulo any number~n, and conclude that the evaluated polynomial f(k) modulo~n depends only on the congruence class of the value~k (at which it was ... 5 n^2-1=(n-1)(n+1) n is not even so n-1 and n+1 are even. Also n=4t+1 or 4t+3, this means at least one of n-1 or n+1 is divisible by 4. n is not 3k so at least one of n-1 or n+1 must be divisible by 3. So n^2-1 has factors of 4, 2(distinct from the 4) and 3 so 24|n^2-1 Edit: I updated my post after arbautjc's correction in his ... 5 Assume u | s and v | t. Since gcd(u, v) | u, therefore gcd(u, v) | s by transitivity of division. Similarly, gcd(u, v) | v, so gcd(u, v) | t as well. Thus, gcd(u, v) is a common divisor of s and t ... Now remember that gcd(s,t) is defined to be the greatest common divisor of s, t i.e. every other common divisor x of s and t will ... 4 The division algorithm on the natural numbers states that for all a,b\in \Bbb N (\in means "in", \Bbb N is all integers greater than 0), there exist q,r\in\Bbb N\cup\{0\} such that a=bq+r and 0\le r<b. The r here is how you define a remainder. Using this: If we are dividing a by 3, the remainder, r, has the restriction 0\le ... 4 To complete the induction, note that a^{k + 1} - b^{k + 1} = a^{k + 1} - a^kb + a^kb - b^{k + 1} = a^k(a - b) + b(a^k - b^k), \tag{1} then simply observe that (a - b) \mid a^k(a - b), \tag{2} which is obvious, and that (a - b) \mid (a^k -b^k) \tag{3} by the induction hypothesis (a - b) \mid (a^k - b^k). \tag{4} Since a - b divides both ... 4 Hints: You are interested in the how many of the numbers 1 - 999, inclusive, satisfy the given conditions. First, let's call X the set of all numbers in our range that are divisible by 7. Then$$|X| = \lfloor 999/7 \rfloor = 142$$Let's call Y the set of all numbers in our range that are divisible by 11.$$|Y| = \lfloor 999/(11) \rfloor = 90$$... 3 c=p\#-x+1 clearly is a solution. Cheap,but a solution. The minimal c if i am not mistaken is conjectured to be at the worst case O(p^2) but i think this is still open. EDIT: It is known from the prime number theorem that ln(p\#)\sim p So if you look at http://oeis.org/wiki/Jacobsthal_function you can see that indeed c\sim O(p^2) is valid if we ... 3 If you have k^3-k divisible by 3, then look at$$(k+1)^3-(k+1)=k^3+3k^2+2k = $$and this is where you need to spot you can use the inductive hypothesis, because you have a k^3 there$$=(k^3-k)+3k^2+3k$$and the term which doesn't have a coefficient 3 is divisible by 3 by the hypothesis. 3 For any integer, there are precisely three options for its reminder when divided by 3, i.e. 0,1,2. So suppose that x_i=3k+i for i=0,1,2. Then$$x_i^2=9k^2+6k+i^2=\begin{cases}3t & i=0\\ 3t+1& i=1,i=2\end{cases}$$So, for any integer x, the reminder of x^2 when divided by 3 is either 0 or 1. Now assume, by the way of contradiction, ... 3 One way to hide the omnipresence of modular arithmetic is to note that a number is divisible by 10 if and only if the final digit is 0; and that the final digit of any number formed by a \{+,-,\times\}-recipe depends only on the final digits of the ingredients. Now, the final digits of the powers of 3 are 1, 3, 9, 7, and then the final ... 3 If d divides P(x),Q(x) d will divide P(x)-Q(x)=x^2-x=x(x-1) But d can not divide x as (P(x),x)=1\implies d will divide x-1 Again, d will divide x^2+x+1-(x^2-x)=2x+1 Again, d will divide 2x+1-2(x-1)=3 Observe that 3 divides P(2013!+1),Q(2013!+1) as 2013!+1\equiv1\pmod3, (2013!+1)^n\equiv1 for any integer n\ge0 3 Let g be a primitive root \pmod{p}. Then the complete set of residues \{1,2,\cdots p-1\}, is, in some order, the same as the set 1,g,g^2,\cdots g^{p-2}. Then we can compute$$ 1^n+2^n+\cdots+(p-1)^n\equiv 1^n+g^n+g^{2n}+\cdots+g^{(p-2)n}\equiv\frac{g^{n(p-1)}-1}{g^n-1}\pmod{p} $$Now as g is a primitive root, g^n\equiv 1 \pmod{p} iff p-1\mid n. ... 3 As a reverse induction using contradiction: Note that for n=0 you have 4|(1-1) and for n=1 you have 4|(5-1). So choose m as the smallest positive integer for which 4\not | (5^m-1) in which case 4\not | (5^m-1-4\times 5^{m-1}) and so 4\not | (5^{m-1}-1) but by the definition of m we know 4 | (5^{m-1}-1), leading to a contradiction, ... 3 I presume you mean (m!)^n divides (mn)!? This is a consequence of the following fact: If \sum a_k = M, then \prod (a_k!) divides M! Their ratio is just the multinomial coefficient, and multiple proofs can be given (search this site). A simple proof is to use induction, with the binomial coefficient as the base case. 2 Assuming that you mean m!^n divides (mn)!, in equation (1) of this answer, it is shown that$$ \frac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} =\prod_{k=1}^n\binom{\displaystyle\sum_{i=1}^ka_i}{a_k} $$If we set all the a_i's to m, we get$$ \frac{(mn)!}{m!^n}=\prod_{k=1}^n\binom{km}{m} $$which gives your result. 2 Let s=uk and t=vn, where k,n \in \mathbb{Z}. Then from the condition of the problem and Bezout's Lemma we have that there exist an integers x,y such that:$$sx + ty = 1ukx + vny = 1u\underbrace{(kx)}_{r} + v\underbrace{(ny)}_{p} = 1ur + vp = 1$$It's trivial that r,p \in \mathbb{Z}. So from Bezout's Lemma this equation has integer ... 2 I think you are misunderstanding the definition of a prime number. A number is said to be prime if it is greater than 1, and its only positive divisors are 1 and itself. A few examples: 2 is a prime number because it is greater than 1, and its only divisors are 1 and 2. You can verify this by noting that \frac{2}{1}=2\in\mathbb{N} and ... 2 First, we want to show that if n is even then n^2 is even. So if n is even what happens? Well, assume n is even. Then what can we say about n? So then n^2=? So then n^2 is even because is of the form 2 \times \text{integer}. Now we need to show the other way around (to get the if and only if, sometimes written iff). So let's assume ... 2 Remainder is what is left when you make integer division. In equations: Say you want to divide p by q. You can always find an integer m and an integer 0\le r<q such that$$p=m\cdot q+r$$or equivalently$$r=p-m\cdot q$$r here is your remainder. For instance if you want to divide p=25 by q=3, you can realize that it the answer is a bit ... 2 Well, the last number divisible by 11 before 7 digits is 999999, so the answer is$$\left\lfloor \frac{9999999-999999}{11}\right\rfloor = 818181.$$More generally, if a is divisible by 11 and b>a, then the number of integers in the half open interval (a, b] divisible by 11 is given by \left\lfloor \frac{b-a}{11} \right\rfloor, as you can verify ... 2 Let's work in \mathbb R^2. We have a linear map given by the matrix$$A=\begin{pmatrix}65 & -56\\1&1\end{pmatrix}$$And we are interested in the solutions to the equation A\mathbf x=\begin{pmatrix}0\\ b\end{pmatrix} where b is an integer. Since the determinant of A is 121, Cramer's rule implies that the first coordinate of the solution ... 2 This isn't completely formal, as usually divisibility is only defined on the integers. However, if we define divisibility on the reals, or say a ring extension of \mathbb{Z}, we can use the generalized definition$$ a\mid b \Longleftrightarrow \exists c\in \mathbb{Z}\text{ such that } b=ac $$In which case your assertion would be correct, taking c=2. 2 You seem to be trying to prove exactly the opposite of what you should be proving. In effect you’re assuming that x^n-1 is divisible by x-1 and showing that x^{n-1}-1 is also divisible by x-1. You should be going in the other direction: for the induction step you want to show that if x^n-1 is divisible by x-1, then x^{n+1}-1 is also divisible ... 2 According to Lucas' theorem, a binomial coefficient \binom{m}{n} is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding digit of m. 2 We can also prove like this : suppose gcd(2n-1,2n+1)=a, then we have$$a|2n-1; a|2n+1$$. So there exists t_1, t_2 such that 2n-1=at_1 and 2n+1=at_2, so from this two equations we get$$at_1+1=at_2-1 \iff a(t_2-t_1)=2. So, $a=1 or 2$, if $a=2$ it contradicts with $a|2n+1$. So, $a=1$

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