If $n \equiv 1\text{ (mod 3)}$ and $n \equiv 3 \text{ (mod 7)},$ what is $n$?

Question

If $n \equiv 1\pmod 3$ and $n \equiv 3 \pmod 7,$ which of the following is $n$?

$10$, $3$, $1$ or $7$.

I tried to solve this using Euler’s theorem and managed to conclude the following:

We have that $\gcd(n, 3)=1$ and that $\gcd(n, 7)=1$.

Now we get that $\phi(3)=2$ which would imply that $n^2 \equiv 1 \pmod 3$.

Similarly $\phi(7)=6$ which in turn implies that $n^6 \equiv 1 \pmod 7.$

Now this is essentially just Fermat’s Little Theorem since we have the congurences in the form $n^{p-1} \equiv 1 \pmod p.$

However I seem to be a bit stuck afterwards. It would seem that $n=1$ would satisfy the two congurences at least(?).

$1^{6} \equiv 1 \pmod 7$ and $1^{2} \equiv 1 \pmod 3.$

Also I’m aware that we could show this just by concluding:

$n \equiv 1 \equiv4 \equiv7 \equiv10 \pmod {3}$ and $n \equiv 3 \equiv 10 \pmod 7.$ Hence $n=10$.

Answer 1

Eep! I didn't realize this was multiple choice!

Sheesh! Just check them.

Is $3 \equiv 1 \pmod 3$? Nope. So that's not it.

Is $1 \equiv 1 \pmod 3$? Yes. Is $1 \equiv 2 \pmod 7$? Nope. So that's not it.

Is $7\equiv 1 \pmod 3$ Yes. Is $1 \equiv 2 \pmod 7$? Nope. So that's not it.

Is $10\equiv 1 \pmod 3$? Yes. Is $10\equiv 3 \pmod 7$. Yes. So that's it.

That's all you had to do.

(Although Chinese Remainder Theorem tells us there can only be one solution $\mod 21$ [$21=3\cdot 7$]).

And Chinese Remainder THeorem says it

======

Euler's theorem is unnecessary (and inapplicable) because you have not exponents to solve

$\gcd(3,7) = 1$ so Chinese remainder Theorem tells us there is one unique solution $\mod 3\cdot 7$. So there is a $n'; 0\le n' < 21$ where $n$ can be any value of $n' + 21m$ for any integer $k$.

And the CRT gives us a methodd of solving for $n'$ but .... I can never remember it.

But knowing it has a solution makes it easy to find. $n = 1+3k= 3 + 7m$ for some $k,m$ and so $3k = 2 + 7m$ and ...

Well, $7m\equiv -2 \pmod 3$ so $6m + m\equiv \equiv -2\pmod 3$ so let $m = 3z - 2$ for some $z$

So $3k = 2+ 7(3z-2)= -12 + 21z$ so $k= -4 + 7z$ so $k \equiv -4\pmod 7$ so let $k=-4 + 7j$ for some $j$.

So we have $3(-4 + 7j)=2+7(3z-2)$ so

$-12+ 21j = -12 + 21z$ so $j = z$. Well, we just need one solution. There are infinitely many so let $j=z =1$ so $k=3$ and $m=1$ and $n=1+3(3)= 3+7(1)=10$. And $n\equiv 10\pmod {21}$.

So $n$ may be any $10 + 21m$ for any integer $m$.

.....

Of course back we we had $3k = 2+7m$ we should have just seen $3*3 = 2+7$.

Answer 2

In general, you can't say what $n$ is. However, it is easy to check which one of those options could be $n$: only $3$ and $10$ are $\equiv 3\pmod 7$, and $3\not\equiv 1\pmod 3$, so it must be $10$.

However, given two congruences $n\equiv a\pmod p$ and $n\equiv b\pmod q$, where $p$ and $q$ have no common factor, the Chinese remainder theorem says there is exactly one value $c\pmod{pq}$ which satisfies them both. So the general solution to your pair of congruences is $n\equiv 10\pmod{21}$.

Answer 3

$n\equiv3\,(mod7)\Longrightarrow n=7k+3\\ n\equiv1\,(mod3) \Longrightarrow 7k+3\equiv1\,(mod3)\,, k\equiv1\,(mod3)\\ \Longrightarrow k=3m+1$ $$n=7k+3 , k=3m+1 \Longrightarrow n= 21m+10$$ only number 10 has this condition with m=0