# Thread: congruence modulo m

1. ## congruence modulo m

Hello, can anyone help me with these two problems?? Thank you so much in advance.

1) Prove: If x ≡ y (mod m), then (x, m) = (y, m)

2) Show that if n > 4 is not prime, then (n-1)! ≡ 0 (mod n).

2. Originally Posted by jenjen
Hello, can anyone help me with these two problems?? Thank you so much in advance.

1) Prove: If x ≡ y (mod m), then (x, m) = (y, m)
Let $\displaystyle x,y,m>0$.

I presume it means $\displaystyle \gcd (x,m)=\gcd (y,m)$.

We know that,
$\displaystyle m|(x-y)$ thus, $\displaystyle x-y=km$ for some $\displaystyle k$.

Let $\displaystyle \gcd(x,m)=d_1$.
Let $\displaystyle \gcd(y,m)=d_2$.
We will prove it by trichtonomy.

Assume $\displaystyle d_1>d_2$.
But that cannot be because,
$\displaystyle y=x-km$
And $\displaystyle d_1|x$ and $\displaystyle d_1|km$.
Thus, $\displaystyle d_1|(x-km)$ thus $\displaystyle d_1|y$. And we also know that $\displaystyle d_1|m$.
Thus, $\displaystyle \gcd(y,m)\not = d_2$ because $\displaystyle d_2<d_1$. And hence it is not "greatest".

By similar reasoning. We can show $\displaystyle d_1<d_2$ leads to contradiction.

Thus, by trichtonomy,
$\displaystyle d_1=d_2$

3. Originally Posted by jenjen
2) Show that if n > 4 is not prime, then (n-1)! ≡ 0 (mod n).
There are two possibilities.

1)n is not a square.

2)n is a square.

If n is not a square then it has a non-trivial proper factorization $\displaystyle n=ab$ where $\displaystyle 2\leq a,b \leq n-1$.
Where $\displaystyle a,b$ are distinct.
Thus among the factors of $\displaystyle (n-1)!$:
$\displaystyle 1,2,3....,n-1$
We can find its factors $\displaystyle a,b$.

When $\displaystyle n$ is a square there are 2 possibilities.
1)n is not a square of a prime.
2)n is a square of a prime.

If n is not a square of a prime we know that $\displaystyle n=c^2=cc=cab$ where $\displaystyle 2\leq a,b\leq c-1$ because it is not a prime. Thus, it has a factorization in the form $\displaystyle n=ab$ where $\displaystyle a,b$ are distinct and the same argument applies.

If n is a square of a prime then we have a minor problem. For example if n=4=2^2 it does not work. Which is why the initial conditions of the problem says n>4. Thus we know that $\displaystyle n=p^2$ and in no other way. We know that $\displaystyle 1,2,...,p,...n-1$ contains one factor. But what about other another factor of $\displaystyle p$? It turns out that when $\displaystyle n>4$ the factor $\displaystyle 2p$ appears among $\displaystyle 1,2,...,n-1$. Thus, there is another number that has a factor of $\displaystyle p$. The reason why is because $\displaystyle p=\sqrt{n}\leq (n-1)/2$ for $\displaystyle n>4$thus, $\displaystyle 2p\leq n-1$ and is hence among one of the factors.

4. thanks theperfecthacker for the quick reply!

5. Originally Posted by ThePerfectHacker
There are two possibilities.

1)n is not a square.

2)n is a square.

If n is not a square then it has a non-trivial proper factorization $\displaystyle n=ab$ where $\displaystyle 2\leq a,b \leq n-1$.
Where $\displaystyle a,b$ are distinct.
Thus among the factors of $\displaystyle (n-1)!$:
$\displaystyle 1,2,3....,n-1$
We can find its factors $\displaystyle a,b$.

When $\displaystyle n$ is a square there are 2 possibilities.
1)n is not a square of a prime.
2)n is a square of a prime.

If n is not a square of a prime we know that $\displaystyle n=c^2=cc=cab$ where $\displaystyle 2\leq a,b\leq c-1$ because it is not a prime. Thus, it has a factorization in the form $\displaystyle n=ab$ where $\displaystyle a,b$ are distinct and the same argument applies.

If n is a square of a prime then we have a minor problem. For example if n=4=2^2 it does not work. Which is why the initial conditions of the problem says n>4. Thus we know that $\displaystyle n=p^2$ and in no other way. We know that $\displaystyle 1,2,...,p,...n-1$ contains one factor. But what about other another factor of $\displaystyle p$? It turns out that when $\displaystyle n>4$ the factor $\displaystyle 2p$ appears among $\displaystyle 1,2,...,n-1$. Thus, there is another number that has a factor of $\displaystyle p$. The reason why is because $\displaystyle p=\sqrt{n}\leq (n-1)/2$ for $\displaystyle n>4$thus, $\displaystyle 2p\leq n-1$ and is hence among one of the factors.
Hmm, you have:

2 <= a,b <= n - 1, shouldn't it be: 1 < a < b < n - 1? Maybe you got it mixed up for when it is a square. The proof I was given was:

Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.

Does this work? It contradicts a few of your results.

6. Originally Posted by Ideasman

Hmm, you have:

2 <= a,b <= n - 1, shouldn't it be: 1 < a < b < n - 1? Maybe you got it mixed up for when it is a square. The proof I was given was:

Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.

Does this work? It contradicts a few of your results.
No. I said proper nontrivial factorization. Meaning the obvious factors, 1 and the number itself are excluded.

7. Originally Posted by ThePerfectHacker
No. I said proper nontrivial factorization. Meaning the obvious factors, 1 and the number itself are excluded.
Sorry to be a pain, but I clearly understand your proof now TPF. What I don't understand is how the proof I was given (below) proves the claim; how does that tie it all together showing that n is composite if n > 4 and that n will then divide (n - 1)!

Proof:

Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.

8. Originally Posted by Ideasman
Sorry to be a pain, but I clearly understand your proof now TPF. What I don't understand is how the proof I was given (below) proves the claim; how does that tie it all together showing that n is composite if n > 4 and that n will then divide (n - 1)!

Proof:

Either n is a perfect square, n = a^2 in which case 2 < a < 2a <= n−1 and hence a and 2a are among the numbers {3,4, . . . ,n−1} or n is not a perfect square, but still composite, with n = ab, 1 < a < b < n−1.
How do you know that 2a<=n-1?
And hence among the factors.
See I acutally used an inequality to justify that.

9. Originally Posted by ThePerfectHacker
How do you know that 2a<=n-1?
And hence among the factors.
See I acutally used an inequality to justify that.
I don't, my professor got that as a proof. But thanks.