Hi!

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

Thanks!

Printable View

- Nov 8th 2009, 08:48 AMBen92non-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! - Nov 8th 2009, 10:21 AMDrexel28
Prove that the congruence has infinite solutions in the natural numbers.**Problem:**

**Proof:**

**Lemma:**

**Proof:**We do this by weak induction.

__Base case:__Merely note that . Now noting that the first term is and that we are multiplying by 5 even numbers gives the desired result.

__Induction hypothesis:__Assume that

__Inductive step:__Merely noting that and using the base case and inductive hypothesis in conjunction finishes the proof.

Now using the above lemma we can clearly see that is a solution for because . And since there are clearly infinite number of natural numbers of the form this provides the desired result.

*Remark:*Choosing 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 . You'll notice that this was possible because when we factored we were left with something of the form where is an even number. Although it wasn't mentioned we only really needed the first three s, the rest were just extra. So in fact we could have gotten by with just 3 or 4 s and in fact any number which factored yields would suffice. For this reason we can actually say that is sufficent for . Also, there is an even "easier" and more general way to do this. I hope that you take the time to explore it. - Nov 8th 2009, 12:52 PMBruno J.
A bit shorter : by Euler's theorem, for any relatively prime to , and for all . Since , and , we have . So .

- Nov 8th 2009, 01:05 PMBen92
Thanks Drexel and Bruno.