Anonymous
Anonymous asked in Science & MathematicsMathematics · 9 years ago

# Prove that 7|(3^(2n)-2^n) for every nonnegative integer n.?

I attempted to use induction, proving that when n=0, the statement is true. Then I assumed it to be true for n=k, and attempted to test it for k + 1, but was unsure as to how to solve it...

Relevance

I don't remember the details of some of these theorems, but what I write below is true.

3^(2n) = (3^2)^n = 9^n. So we have 9^n - 2^n. Because 9 = 2+7, 9^n (mod 7) = 2^n (mod 7). Thus, we have 9^n - 2^n (mod 7) = 2^n - 2^n (mod 7) = 0 (mod 7). Therefore, it is divisible by 7. Note: The "=" signs should be the three-lined equivalent signs.

• i think of you propose n^3 + 2n Induction will sparkling up this. For base case n = a million, a million^3 + 2 = 3 is divisible via 3. anticipate it incredibly is actual for all n = ok -> ok^3 + 2k is divisible via 3. enable ok^3 + 2k = 3m (m is an integer) Proving for n = ok + a million (ok + a million)^3 + 2(ok + a million) = ok^3 + a million + 3k^2 + 3k + 2k + 2 = (ok^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3k^2 + 3k + 3 = 3(m + ok^2 + ok + 3) that's divisible via 3 considering that n = ok is actual implies n = ok + a million is actual, and since the backside case is actual to boot, n^3 + 2n is divisible via 3 for all n ? Z

• An easy proof:

3^(2n) - 2^n = 9^n - 2^n

Lemma: (a-b) | (a^n - b^n) [THIS IS actually a very important fact]

Proof: Consider the expression a^(n-1) * b + a^(n-2) * b^2 + ... a^2 * b^(n-2) + a * b^(n-1)

Write this in terms of a geometric series (it may take you a while to see this)

(a^(n-1) * b)((b/a)^(n-1) - 1)

--------------------------------------

(b/a) - 1

after loads of simplification, this becomes [ab(a^n - b^n)]/(a-b)

however since we know that expression is an integer, (a-b) | (a^n - b^n)

hence, (9-2) | (9^n - 2^n) ==> 7 | (3^(2n) - 2^n)

• 7 | (3²ⁿ - 2ⁿ) ⇔ 3²ⁿ - 2ⁿ = 7u ⇔ 9ⁿ - 2ⁿ = 7u, where u ∈ ℤ

9ⁿ = (2+7)ⁿ = C(n,0)(2ⁿ)(7⁰) + C(n,1)(2ⁿ⁻¹)(7) + C(n,2)(2ⁿ⁻²)(7²) + ... + C(n,n-1)(2¹)(7ⁿ⁻¹) + C(n,n)(2⁰)(7ⁿ)

9ⁿ - 2ⁿ = 2ⁿ + C(n,1)(2ⁿ⁻¹)(7) + C(n,2)(2ⁿ⁻²)(7²) + ... + C(n,n-1)(2¹)(7ⁿ⁻¹ + C(n,n)(2⁰)(7ⁿ) - 2ⁿ

= C(n,1)(2ⁿ⁻¹)(7) + C(n,2)(2ⁿ⁻²)(7²) + ... + C(n,n-1)(2¹)(7ⁿ⁻¹) + C(n,n)(2⁰)(7ⁿ)

= 7(C(n,1)(2ⁿ⁻¹) + C(n,2)(2ⁿ⁻²)(7¹) + ... + C(n,n-1)(2¹)(7ⁿ⁻²) + C(n,n)(2⁰)(7ⁿ⁻¹))

= 7u

u = (C(n,1)(2ⁿ⁻¹) + C(n,2)(2ⁿ⁻²)(7¹) + ... + C(n,n-1)(2¹)(7ⁿ⁻²) + C(n,n)(2⁰)(7ⁿ⁻¹))