non-linear congruence proof

Ben92 · #1 $Old$ November 8th, 2009, 09:48 AM

Hi!

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

Thanks!

Drexel28 · #2 $Old$ November 8th, 2009, 11:21 AM

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\cdot64m+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 $e$ s, the rest were just extra. So in fact we could have gotten by with just 3 or 4 $e$ s 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.

Bruno J. · #3 $Old$ November 8th, 2009, 01:52 PM

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$ .

Ben92 · #4 $Old$ November 8th, 2009, 02:05 PM

Thanks Drexel and Bruno.