Linear congruence equations

65 Views Asked by At

I'm trying to prove that the following system of congruence equations has a solution:

$X \equiv 2 $ (mod $5^N$)

$X \equiv 1 $ (mod $7^N$)

$X \equiv 4 $ (mod $6^N-4$)

being $N$ an integer number, $N\geq 2$

I guess that this may be answered using the Chinese Remainder Theorem, for which I need to show that the numbers $5^N$, $7^N$, $6^N-4$ are pairwise coprimes integers. I can see that this is certainly the case between $5^N$ an $7^N$ because $5$ and $7$ are prime integers, but I am not being able to see it between $5^N$ (or $7^N$) and $6^N-4$.

Maybe someone can help me to see why they are coprimes or perhaps, if I am not on the right track, suggest me another way of proving the existence of the solution of the system.

2

There are 2 best solutions below

0
On BEST ANSWER

Notice that neither $5$ nor $7$ is ever a prime factor of $6^N-4$. I'll do the case with $5$ and leave the $7$ case for you to check; having checked these two cases we can safely conclude that the three numbers in question are relatively prime because the only prime factors of $5^N$ and $7^N$ are $5$ and $7$, respectively (so none of the three numbers will share any prime factors).

By contradiction, suppose $6^N-4$ has $5$ as a prime factor for some $N\geq 2$, and thus $6^N-4\equiv 0\pmod 5$. Then $6^N\equiv 4\pmod 5$ and thus $1^N\equiv 4\pmod 5$ since $6\equiv 1\pmod 5$. This is absurd since $1^N=1$ and $1\not\equiv 4\pmod 5$. Hence, $5$ is never a prime factor of $6^N-4$ for any $N$.

0
On

$6^N-4 \equiv 1^N-4 \equiv 2 \pmod 5$

So $1 = \gcd(5,6^N-4) = \gcd(5^N,6^N-4)$

$6^N-4 \equiv (-1)^N-4 \in \{2, 4\} \pmod 7$

So $1 = \gcd(7,6^N-4) = \gcd(7^N,6^N-4)$