1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.