Thread: [SOLVED] two questions I am stumped on

1. [SOLVED] two questions I am stumped on

Hi, first post here though I have been using the search feature to help myself through an onlin Intro to Number Theory class. I am stumped on two congruence questions.

1. If n>4 is a composite number, show that n|(n-1)! Conclude that (n-1)! not congruent -1(mod n).

(This shows that Wilson's theorem can be used as a proof of primality. It is unfortunately not practical for large numbers)

2. Use the congruence equation x^2 - 1 congruent 0(mod p) to show that if (a,p) = 1, then a^((p-1)/2) congruent +/- 1(mod p).

I in words why a composite (ab) number does not work, but am not really sure how to prove it. And for the second one, I do not really know how to start. Any help would be greatly appreciated as searching did not turn up anything really helpful to me.

2. Hi,
Originally Posted by Proggy
Hi, first post here though I have been using the search feature to help myself through an onlin Intro to Number Theory class. I am stumped on two congruence questions.

1. If n>4 is a composite number, show that n|(n-1)! Conclude that (n-1)! not congruent -1(mod n).

(This shows that Wilson's theorem can be used as a proof of primality. It is unfortunately not practical for large numbers)

2. Use the congruence equation x^2 - 1 congruent 0(mod p) to show that if (a,p) = 1, then a^((p-1)/2) congruent +/- 1(mod p).

I in words why a composite (ab) number does not work, but am not really sure how to prove it. And for the second one, I do not really know how to start. Any help would be greatly appreciated as searching did not turn up anything really helpful to me.
I have little time... but I'll try.

For the first one, consider that (n-1)! contains any integer inferior or equal to n-1 as a factor, that is to say any integer inferior to n. Now, if n is a composite number, then it's the product of at least 2 integers that are inferior to n. But these 2 numbers are in the product (n-1)!. Thus you can retrieve n in (n-1)! --> n divides (n-1)!
I hope it's clear enough... !

3. Originally Posted by Moo
Hi,

I have little time... but I'll try.

For the first one, consider that (n-1)! contains any integer inferior or equal to n-1 as a factor, that is to say any integer inferior to n. Now, if n is a composite number, then it's the product of at least 2 integers that are inferior to n. But these 2 numbers are in the product (n-1)!. Thus you can retrieve n in (n-1)! --> n divides (n-1)!
I hope it's clear enough... !
So since a|(n-1)! and b|(n-1)!, then ab|(n-1)!. That helps, I can flesh it out from there. One thing I wonder though, it seems to me that this method might be thrown off if a=b?

And no worries on the time, I appreciate any help. I am on lesson 12 of 16 lessons in the course. I have struggled through up to this point, but some of these problems are leaving me not even knowing where to start. The book states a theorem and the proof, but it leaves a lot to the imagination as it does not give much in the way of actual examples of using the theorems to solve problems. I do not mean to look like I am not trying. I find that one of two things happens with my homework. Most of the time I figure out a starting point and manage my way to a solution. But I am finding a few problems where I just do not know how to start and those make it look like I am not trying.

5. Originally Posted by ThePerfectHacker
Thanks TPH, I had done a search on congruence and with all the threads to read I had skipped that one due to the title referring to the first of the two problems in the thread. That definitely answered my question of when a=b, or n=a^2.

Though it is obviously true from your proof, I would not have known immediately that...
Originally Posted by ThePerfectHacker
The reason why is because for thus, and is hence among one of the factors.
I would very much appreciate any hints on how to begin the second problem. Will spend some more time tomorrow clicking every searched thread containing congruence.

6. #2 is known as Euler's criterion .. or at least it's part of it anyway.

Let $\displaystyle g$ be a primitive root of $\displaystyle p$. Then, $\displaystyle a \equiv g^{k} \: (\text{mod } p)$ for some k since $\displaystyle a$ is a least residue mod p and all the powers of $\displaystyle g$ from 1 to $\displaystyle \phi(p) = p -1$ are a permutation of all least residues relatively prime to p (which is what we have since (a, p) = 1.

If k is even, then $\displaystyle a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{k/2})^{(p-1)} \equiv 1 \: (\text{mod } p)$ by Fermat's theorem.

If k is odd, then $\displaystyle a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{(p-1)/2})^{k} \equiv (-1)^{k} \equiv -1 \: ( \text{mod } p)$

7. Originally Posted by o_O
#2 is known as Euler's criterion .. or at least it's part of it anyway.

Let $\displaystyle g$ be a primitive root of $\displaystyle p$. Then, $\displaystyle a \equiv g^{k} \: (\text{mod } p)$ for some k since $\displaystyle a$ is a least residue mod p and all the powers of $\displaystyle g$ from 1 to $\displaystyle \phi(p) = p -1$ are a permutation of all least residues relatively prime to p (which is what we have since (a, p) = 1.

If k is even, then $\displaystyle a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{k/2})^{(p-1)} \equiv 1 \: (\text{mod } p)$ by Fermat's theorem.

If k is odd, then $\displaystyle a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{(p-1)/2})^{k} \equiv (-1)^{k} \equiv -1 \: ( \text{mod } p)$
Can that be done without the use of primitive roots? This is a problem from section 3.6 in the book and section 3.7 is titled Primitive Roots, so the book is not expecting me to know about those yet.

8. how about the Legendre's Number? are you allowed to use it?

9. Originally Posted by kalagota
how about the Legendre's Number? are you allowed to use it?
I did not recognize the name, so I checked the index and Legendre only shows up once, on page 2 no less, concerning his thoughts that helped lead to the prime number theorem. So I guess no, I can not use it.

The section I am doing this problem from is named Polynomial Congruences. It includes distinct solutions to congruent polynomials, a couple unnamed theorems that I can not seem to apply to this problem and Wilson's Theorem.

10. Originally Posted by Proggy
Use the congruence equation x^2 - 1 congruent 0(mod p) to show that if (a,p) = 1, then a^((p-1)/2) congruent +/- 1(mod p).
If $\displaystyle \gcd(a,p)=1$ then $\displaystyle a^{p-1}\equiv 1(\bmod p)$.
Thus, $\displaystyle a^{p-1} - 1\equiv 0 (\bmod p)$.
Thus, $\displaystyle (a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 (\bmod p)$ ---> if $\displaystyle p\not = 2$.
Thus, $\displaystyle a^{(p-1)/2} \equiv \pm 1(\bmod p)$.

11. Originally Posted by ThePerfectHacker
If $\displaystyle \gcd(a,p)=1$ then $\displaystyle a^{p-1}\equiv 1(\bmod p)$.
Thus, $\displaystyle a^{p-1} - 1\equiv 0 (\bmod p)$.
Thus, $\displaystyle (a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 (\bmod p)$ ---> if $\displaystyle p\not = 2$.
Thus, $\displaystyle a^{(p-1)/2} \equiv \pm 1(\bmod p)$.

Wouldn't the first line be dependent on p being prime? That is one of the requirements of Fermat's Theorem? Other than being confused on the first assumption, I followed the rest of it easy enough. And that confusion is what prevented me from starting out that way in the first place. I am obviously just missing something easy?

12. Originally Posted by Proggy
Wouldn't the first line be dependent on p being prime? That is one of the requirements of Fermat's Theorem? Other than being confused on the first assumption, I followed the rest of it easy enough. And that confusion is what prevented me from starting out that way in the first place. I am obviously just missing something easy?
in fact, that line is the fermat's little theorem itself..
haven't you proved that yet?

13. Originally Posted by kalagota
in fact, that line is the fermat's little theorem itself..
haven't you proved that yet?
yes, but in the book, the theorem starts with "Suppose p is a prime. Then for all a"...then the formula. The p-1 is based on the number of integers in a reduced residue system, which for prime p is p-1, but if p is not prime, then it would not be p-1. That is the way my intro book explains it and that is why that first line confuses me.

14. well, if p were not prime, then it would be useless to talk about the formula.

15. okay, I just realized what I might have not have been taking as an assumption before. In Number Theory, if they use p to represent a number in a theory, is it to be assumed that p is prime even without explicitly stating it, such as in the problem I posted in the original post? I was assuming that when talking about a prime number, you used p to represent it. BUt I had not been assuming that all p's would then imply a prime number. It makes sense, but if I have learned anything in this class, it has been to not take anything for granted.

Page 1 of 2 12 Last