Results 1 to 5 of 5

Thread: Divisibility Proofs

  1. July 16th 2012, 06:40 AM #1
    GrigOrig99
    GrigOrig99 is offline
    Member
    Joined
    Jul 2011
    Posts
    138

    Divisibility Proofs

    Can anyone help me confirm if I've solved this correctly?

    Many thanks.

    Q.     7^n+4^n+1 is divisible by 6 for n \in \mathbb{N}

    Attempt: Step 1: For n = 1...
    7^1+4^1+1=12, which can be divided by 6.
    Therefore, n = 1 is true...

    Step 2: For n = k...
    Assume 7^k+4^k+1 can be divided by 6,
    i.e. 7^k+4^k+1=6Z, where Z is an integer...1
    Show that n = k + 1 is true...
    i.e. 7^{k+1}+4^{k+1}+1 can be divided by 4
    7^{k+1}+7\cdot4^k-7\cdot4^k+4^{k+1}+1 => 7(7^k+4^k)+4^k(7-4)+1...from 1 above => 7(6Z-1)+4^k\cdot3+1 => 42Z-7+4^k\cdot3+1 => 42Z+4^k\cdot3-6 => 84Z+4^k\cdot6-12 => 6(14Z+4^k-2)
    Thus, assuming n = k, we can say n = k + 1 is true and true for n = 2, 3,... and all n \in \mathbb{N}_0
    Follow Math Help Forum on Facebook and Google+
  2. July 16th 2012, 07:30 AM #2
    emakarov
    emakarov is offline
    MHF Contributor
    Joined
    Oct 2009
    Posts
    4,883
    Thanks
    457

    Re: Divisibility Proofs

    The idea is correct, but there are several small flaws.

    Quote Originally Posted by GrigOrig99 View Post
    Therefore, n = 1 is true...
    Rather, P(1) is true where P(n) is " 7^n+4^n+1 is divisible by 6."

    Quote Originally Posted by GrigOrig99 View Post
    Show that n = k + 1 is true...
    Should be: "Show that P(k + 1) is true."

    Quote Originally Posted by GrigOrig99 View Post
    i.e. 7^{k+1}+4^{k+1}+1 can be divided by 4
    By 6.

    Quote Originally Posted by GrigOrig99 View Post
    7^{k+1}+7\cdot4^k-7\cdot4^k+4^{k+1}+1 => 7(7^k+4^k)+4^k(7-4)+1
    (7 - 4) should be (4 - 7).

    Quote Originally Posted by GrigOrig99 View Post
    ...from 1 above => 7(6Z-1)+4^k\cdot3+1 => 42Z-7+4^k\cdot3+1 => 42Z+4^k\cdot3-6 => 84Z+4^k\cdot6-12 => 6(14Z+4^k-2)
    What exactly does => mean here? Especially, what is the relationship between 42Z+4^k\cdot3-6 and 84Z+4^k\cdot6-12?

    Quote Originally Posted by GrigOrig99 View Post
    Thus, assuming n = k, we can say n = k + 1 is true
    Assuming n = k, the fact that n = k + 1 is obviously false.

    Edit: Added remark about 4 - 7.
    Last edited by emakarov; July 16th 2012 at 07:33 AM.
    Follow Math Help Forum on Facebook and Google+
  3. July 16th 2012, 07:31 AM #3
    Prove It
    Prove It is online now
    MHF Contributor Prove It's Avatar
    Joined
    Aug 2008
    Posts
    10,253
    Thanks
    695

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    Can anyone help me confirm if I've solved this correctly?

    Many thanks.

    Q.     7^n+4^n+1 is divisible by 6 for n \in \mathbb{N}

    Attempt: Step 1: For n = 1...
    7^1+4^1+1=12, which can be divided by 6.
    Therefore, n = 1 is true...

    Step 2: For n = k...
    Assume 7^k+4^k+1 can be divided by 6,
    i.e. 7^k+4^k+1=6Z, where Z is an integer...1
    Show that n = k + 1 is true...
    i.e. 7^{k+1}+4^{k+1}+1 can be divided by 4
    7^{k+1}+7\cdot4^k-7\cdot4^k+4^{k+1}+1 => 7(7^k+4^k)+4^k(7-4)+1...from 1 above => 7(6Z-1)+4^k\cdot3+1 => 42Z-7+4^k\cdot3+1 => 42Z+4^k\cdot3-6 => 84Z+4^k\cdot6-12 => 6(14Z+4^k-2)
    Thus, assuming n = k, we can say n = k + 1 is true and true for n = 2, 3,... and all n \in \mathbb{N}_0
    You have a sign error.

    \displaystyle \begin{align*} 7^{k + 1} + 4^{k + 1} + 1 &= 7^{k + 1} + 7 \cdot 4^k - 7 \cdot 4^k + 4^{k + 1} + 1 \\ &= 7\left(7^k + 4k\right) - 4^k\left(7 - 4\right) + 1 \\ &= 7\left(6Z - 1\right) - 3\cdot 4^k + 1 \\ &= 42Z - 7 - 3\cdot 4^k + 1 \\ &= 42Z - 3\cdot 4^k - 6 \\ &= 42Z - 3\cdot 4 \cdot 4^{k - 1} - 6 \\ &= 6\left(7Z - 2\cdot 4^{k - 1} - 1\right) \end{align*}
    Follow Math Help Forum on Facebook and Google+
  4. July 16th 2012, 07:42 AM #4
    GrigOrig99
    GrigOrig99 is offline
    Member
    Joined
    Jul 2011
    Posts
    138

    Re: Divisibility Proofs

    Ok, thanks guys,
    Follow Math Help Forum on Facebook and Google+
  5. July 16th 2012, 10:17 AM #5
    richard1234
    richard1234 is offline
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    96

    Re: Divisibility Proofs

    Another way to do it:

    7^n \equiv 1^n \equiv 1 (\mod 6)

    4^n \equiv 4 (\mod 6) (this is a little hard to prove, but checking the first few cases you will see that it always works).

    Therefore, 7^n + 4^n + 1 \equiv 1 + 4 + 1 \equiv 0 (\mod 6), therefore it is always divisible by 6.
    Follow Math Help Forum on Facebook and Google+
« Sketching a graph from limt information | give the argument in radians and solve »

Similar Math Help Forum Discussions

  1. Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: July 7th 2012, 09:22 AM
  2. Proof by Induction - Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: September 26th 2011, 03:51 AM
  3. Proof by Induction - Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: September 20th 2011, 04:29 PM
  4. Proofs of rules of divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 24th 2010, 10:47 AM
  5. Proofs-Divisibility of Integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 14th 2009, 11:45 PM

Search Tags


/mathhelpforum @mathhelpforum