Show that for any k∈N, if $2^{3k-1} +5\cdot3^k$ is divisible by 11 then, $2^{3^{(k+2)-1}} +5\cdot3^{k+2}$ is divisible by 11.  Base Case: k = 2  $\implies2^{3*2-1} +\cdot3^2 =77$  Since 77 is divisible by 11, the base case holds true  I.H: Assume it is true for  $2^{3x-1} +5\cdot3^x$,x∈N  Then; for k=x+1  $$\implies 2^{3(x+1)-1} +5\cdot3^{x+1}$$ $$\implies 2^{3x-1}\cdot2^3 +5\cdot(3^x\cdot3^1)$$ $$\implies 2^{3x-1}\cdot8 +15\cdot3^x$$  How do i proceed from what i have so far, also what variable do i use since k is already been used?
123907
Question:  Part a:  Prove that for any $ b\in \Bbb N,$ if $ 2^{3b -1} + 5 . 3^{b}$ is divisible by $ 11$, then $ 2^{3(b+2) -1} + 5 . 3^{b+2}$ is divisible by $11$.  Part b:  Is statement 1 or statement 2 true? Explain answer.   For any odd number $a\in \Bbb N $, $ 2^{3a -1} + 5 . 3^{a}$ is divisible by $ 11$ For any even number $a\in \Bbb N $, $ 2^{3a -1} + 5 . 3^{a}$ is divisible by $ 11$   My attempt:  Part a:  I am not sure what the base case should be.  Induction hypothesis: Assume $ 2^{3k -1} + 5 . 3^{k}$ is divisible by $ 11$, for some $k$ natural number.   I am not sure how to prove true for $ 2^{3(k+2) -1} + 5 . 3^{k+2}$.  Part b:  Would statement 2 be correct since the expression is divisible by $11$ when $ a=2$
47177
There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example of course.  Tried using $\gcd(2^a+1, 2^b+1) = 2^{\gcd(a, b)}+1$ (where $a$ and $b$ are odd positive integers), stuck on both ends. I figured out that if $n$ divides $2^n+1$ then n divides both $2^{2^n+1}+1$ and $2^{2^{2^n+1}+1}+1$ but this implication doesn't work backwards (e.g. $n=57$).  Would appreciate some help.  EDIT1 Eric's pointer wasn't enough for me. Trying to bump by editing instead of reposting (sorry, not sure how to).  EDIT2 This is not much but might save some time for someone. Using user101140's notation and the $a^n+b^n$ identity  $f(n) = 2^n+1 = 3 \sum\limits_{k=0}^{n-1} (-2)^k$  $f(f(n)) = 3 \sum\limits_{k=0}^{2^n} (-2)^k$  $f(f(f(n))) = 3 \sum\limits_{k=0}^{2^{2^n+1}} (-2)^k$  Also, $n \mid f(n) \implies n \mid f(f(n))$ is due to $n \mid f(n) \implies f(n) \mid f(f(n))$ so the proof might be something along the lines of $n \mid f(f(n)) \implies f(f(n)) \mid f(f(f(n)))$. (Please don't bash me if that's stupid.)
50190
I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9.   Usually with these divisibility induction problems, it falls apart nicely and we can easily factorise say a 9 if the question required us to prove that the expression is divisible by 9. However in this case, I do not end up with such a thing.  My work so far below:  Inductive Hypothesis: $7^k(3k+1)-1=9N$ where $N\in\mathbb{N}$  Inductive Step:  $7^{k+1}(3k+4)-1 \\ =7\times 7^k(3k+1+3)-1 \\ =7\times \left [ 7^k(3k+1)+3\times 7^k \right ] -1 \\ = 7 \times \left [ 9N+1 + 3 \times 7^k \right ] -1 \\ = 63N+21\times 7^k+6 \\ = 3 \left [ 21N+7^{k+1}+2 \right ]$   So now I need to somehow prove that $21N+7^{k+1}+2$ is divisible by 3, but I'm not quite sure how to proceed from here...
85270
I have observed that all numbers of the form $10^{k} + 1$ are composite for $k{\gt}2$, and am trying to prove the same.   Progress  For odd $k$ , it is fairly obvious, as we get 11 as a divisor.  I am having difficulty with $k$ even. Have no clue how to approach. Would prefer a non-inductive approach, if possible  Developments  Thanks to crostul, we can say it is composite for $k$ having an odd divisor. Hence, it only remains to prove it for $k = 2^n$
50414
As part of a larger proof, I need to show why $a^3-a$ is always divisible by $6$. I'm having trouble getting started.
114710
Find the quotient and remainder when $6x^4-11x^3+5x^2-7x+9$ is divided by $(2x-3)$. I expressed the divisor $(2x-3)$ as $2(x-\frac{3}{2})$ and conducted synthetic division by $\frac{3}{2}$ and obtained the coefficients of the quotients as $6, -2, 2$ and $-4$ and the remainder as $3$. Then I divided the quotients by $2$. Why should I do this? and why should I not divide the remainder by $2$?
69085
Prove by mathematical induction that $2^{3^n}+1$ is divisible by $3^{n+1}.$   I'm currently trying to finish a task that requires me to use mathematical induction to prove that $2^{3^n}+1$ is divisible by $3^{n+1}$. This is the first time that the divider is not a simple integer and I'm having trouble trying to prove it.   This is what I managed to do:     First step:      For $n=1$:      $2^3+1=9$      $3^2=9$      $L=P$      Second step: I assume that for some numbers $n&gt;=1$  $2^{3^n}+1$ is divisible by $3^{n+1}$      Third step: (induction hypothesis):   $2^{3^{n+1}}+1$ is divisible by $3^{n+1}$   I'm getting stuck here, trying to do some algebra and simplify the dividend:     $2^{3^{n+1}}+1 = 2^{3^n*3}+1$
38959
So I started with a base case $n = 1$. This yields $5|0$, which is true since zero is divisible by any non zero number. I let $n = k &gt;= 1$ and let $5|A = (k^5-k)$. Now I want to show $5|B = [(k+1)^5-(k+1)]$ is true....  After that I get lost.   I was given a supplement that provides a similar example, but that confuses me as well.   Here it is if anyone wants to take a look at it:  Prove that for all n elements of N, $27|(10n + 18n - 1)$.  Proof:  We use the method of mathematical induction. For $n = 1$, $10^1+18*1-1 = 27$.  Since $27|27$, the statement is correct in this case.  Let $n = k = 1$ and let $27|A = 10k + 18k - 1$.  We wish to show that $27|B = 10k+1 + 18(k + 1) - 1 = 10k+1 + 18k + 17$.  Consider $C = B - 10A$ ***I don't understand why A is multiplied by 10. $= (10k+1 + 18k + 17) - (10k+1 + 180k - 10)$    $= -162k + 27 = 27(-6k + 1)$.  Then $27|C$, and $B = 10A+C$. Since $27|A$ (inductive hypothesis) and $27|C$, then $B$ is the sum of two addends each divisible by $27$. By Theorem 1 (iii), $27|B$, and the proof is complete.
58168
I have just proved the divisibility rule for 3 and 9.  Let $n\in\mathbb{N}$. Let $m$ be a number that appears when you shuffle the digits in $n$. Show that $n-m$ is a multiple of 9.  Can anyone offer some help?
76046
Suppose $k\in\mathbb N$ and suppose $2^k+1=u^2$ and $2^k-1=v^2$ for some $u,v\in\mathbb N$. I have to prove that the first case implies $k=3$ and the second case implies $k=1$. Also, for the second case it is hinted to use the fact (lemma) that if $n$ is odd, then $n^2\equiv1 \pmod 8$, but I suppose it could be used for the first one as well. My progress so far:     First question:      Suppose $u$ is even, then $u=2t$ for some $t\in\mathbb N$, thus $u^2=4t^2=2^k+1$. Notice that two divides the left hand side of the equation, therefore it also divides the right hand side. Since it divides $2^k$ for any $k\ge1$, it must also divide $1$, contradiction. So $u$ is odd and therefore $u^2\equiv1\pmod 8$. Thus there exists an $m\in\mathbb Z$ such that $u^2=8m+1=2^k +1$. Thus $2^k=8m$, therefore $k\ge3$.   I am stuck at this point, however. I suppose setting $k&gt;3$ and finding a contradiction would be a possible method, but I do not know what $k&gt;3$ actually has to offer to solve this problem. No other method I think of gets me anywhere, either. I guess I could try to show that $2^k+1$ cannot be a square for $k&gt;3$. Perhaps I could use the fact that $u^2-2^k=1$ or that $\gcd(u^2,2^k)=1$.     Second question:      The same reasoning can be applied to show that $v$ has to be even. Therefore, according to the lemma proposed above, $2^k-1=v^2\equiv1\pmod 8$. This implies $2^k\equiv2\pmod 8$. For any $k\ge3$ there exists some $t\in \mathbb N$ such that $2^k=8t$, therefore $2^k\equiv0\pmod 8$, which leads to a contradiction. Checking for $k=1,2$ leads to the conclusion that $k=1$ is the only possibility.   I think I have actually figured out this proof while writing down the progress I already have made, but for the sake of completeness and to check it's correctness I will leave it here.
44996
i would like to know how to prove that if $a^2+b^2=c^2$ then   a) $3|a$ or $3|b$  b) $5|a$ or $5|b$ or $5|c$  c) $4|a$ or $4|b$   Also that $a^2+b^2+c^2+1$ can't be divisible by 8  Thank you very much!
64652
Is there any difference in proving "for any integer $n &gt; 0$, $3|(5^{2n}-1)$" and proving "for any integer $n \ge 0$, $3|(5^{2n} -1)$"? Or are they the same?
22988
Prove that if $d$ divides $n$, then $2^d  -1$ divides $2^n  -1$.  Use the identity $x^k  -1 = (x-1)*(x^{k-1}  +  x^{k-2}    + \cdots + x +1)$
54109
Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.   I thought I would do the following ... As $n$ is not divisible by $2$ and $3$ then $$n=2k+1\;\text{or}\\n=3k+1\;\text{or}\\n=3k+2\;\;\;\;$$for some $n\in\mathbb{N}$. And then make induction over $k$ in each case.$$24\mid (2k+1)^2-1\;\text{or}\\24\mid (3k+1)^2-1\;\text{or}\\24\mid (3k+2)^2-1\;\;\;\;$$This question is in a text of Euclidean Division I'm reviewing, and I wonder if there is a simpler, faster, or direct this way.
54819
I've been working through a bit of Ireland and Rosen's Number Theory for fun. Problem 4.11 of Ireland and Rosen asks     Prove that $1^k+2^k+\cdots+(p-1)^k\equiv 0\pmod{p}$ if $p-1\nmid k$, and $-1\pmod{p}$ if $p-1\mid k$.    My work is leading where I didn't expect to go. Here I assume $p$ id odd. First, if $p-1\mid k$, then we can wrike $k=(p-1)j$ for some $j$. But then $$ 1^k+\cdots+(p-1)^k\equiv 1^{(p-1)j}+\cdots+(p-1)^{(p-1)j}\equiv \underbrace{1+\cdots+1}_{p-1\text{ times}}=\frac{(p-1)p}{2}\equiv 0\pmod{p} $$ since $p-1$ is even.   Secondly, I suppose $p-1\nmid k$. WLOG, I can assume $0&lt;k&lt;p-1$, Since if $k=(p-1)j+r$ with $0&lt;r&lt;p-1$, then  $$ a^k\equiv a^{(p-1)j+r}\equiv a^r\pmod{p}. $$  Then if $g$ is a primitive root, $$ 1^k+\cdots+(p-1)^k=\sum_{i=1}^{p-1}(g^k)^i=\frac{g^k(1-g^{k(p-1)})}{1-g^k}. $$ Since $g$ is primitive, $p\nmid 1-g^k$, but $p\mid 1-g^{k(p-1)}$, so the above sum is again congruent to $0\pmod{p}$.  So in all cases, I get the sum is congruent to $0$ regardless. Have I messed up, or is there a typo? Thanks.
107067
How do you prove that a number is divisible by 3 iff the sum of its digits is divisible by 3? Please avoid using the modulus or any other operations or advanced terminology from number theory because I have never taken that class.
54300
Yeah so I'm kind of stuck on this problem, and I have two questions.   Is there a way to define a number mathematically so that it cannot be a multiple of $7$? I know $7k+1,\ 7k+2,\ 7k+3,\ \cdots$, but that will take ages to prove for each case.  Is this a proof? $$(7k + a)^3 \equiv (0\cdot k + a)^3 \equiv a^3 \bmod 7$$    Thank you.