How do i proof that 9^(n+1) == 8n+9 (mod 64) congruence has infinite solutions if n is a natural number?
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.