Results 1 to 4 of 4

Math Help - non-linear congruence proof

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    16

    non-linear congruence proof

    Hi!

    How do i proof that 9^(n+1) == 8n+9 (mod 64) congruence has infinite solutions if n is a natural number?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Ben92 View Post
    Hi!

    How do i proof that 9^(n+1) == 8n+9 (mod 64) congruence has infinite solutions if n is a natural number?

    Thanks!
    Problem: Prove that the congruence 9^{n+1}\equiv8n+9\text{ mod }64 has infinite solutions in the natural numbers.

    Proof:

    Lemma: 9^{64n}\equiv 1\text{ mod }64\quad\forall n\in\mathbb{N}

    Proof: We do this by weak induction.

    Base case: Merely note that 9^{64}-1=\left(9^{32}-1\right)\left(9^{32}+1\right)=\cdots=\left(9^1-1\right)\cdot(9^1+1)\cdot(9^2+1)\cdots\left(9^{32}  +1\right). Now noting that the first term is 9-1=8 and that we are multiplying by 5 even numbers gives the desired result.

    Induction hypothesis: Assume that 9^{64n}\equiv1\text{ mod }64

    Inductive step: Merely noting that 9^{64(n+1)}=9^{64n}\cdot9^{64} and using the base case and inductive hypothesis in conjunction finishes the proof.


    Now using the above lemma we can clearly see that n=64m is a solution for m\in\mathbb{N} because 9^{64m+1}=9^{64m}\cdot9^1\equiv9\equiv0+9\equiv8\c  dot64m+9. And since there are clearly infinite number of natural numbers of the form 64m this provides the desired result.



    Remark: Choosing n=32m would work equally as well.

    EDIT: I feel as though I should explain my "remark" better. The operative part of this proof is that we needed 64|9^{64}-1. You'll notice that this was possible because when we factored 9^{64}-1 we were left with something of the form 8\cdot e \cdot e \cdot e \cdot e \cdot e where e is an even number. Although it wasn't mentioned we only really needed the first three es, the rest were just extra. So in fact we could have gotten by with just 3 or 4 es and in fact any number which factored yields 8\underbrace{e\cdot e\cdot e\cdots}_{\ge3} would suffice. For this reason we can actually say that n=2^xm is sufficent for x\ge4. Also, there is an even "easier" and more general way to do this. I hope that you take the time to explore it.
    Last edited by Drexel28; November 8th 2009 at 10:52 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    A bit shorter : by Euler's theorem, a^{k\phi(m)}\equiv 1 \mod m for any a relatively prime to m, and for all k \in \mathbb{Z}. Since \phi(64)=32, and (9,64)=1, we have 9^{32k} \equiv 1 \mod 64. So 9^{32k+1}\equiv 9 \equiv 9+8\times 32k \mod 64.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2009
    Posts
    16
    Thanks Drexel and Bruno.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solve linear congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 23rd 2010, 03:50 AM
  2. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 05:11 AM
  3. Solving a linear congruence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 06:54 PM
  4. Linear congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2009, 05:48 AM
  5. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 3rd 2008, 10:04 AM

Search Tags


/mathhelpforum @mathhelpforum