[SOLVED] two questions I am stumped on

**Proggy** · August 17th 2008, 12:39 PM

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.

**Moo** · August 17th 2008, 06:02 PM

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

**Proggy** · August 17th 2008, 06:10 PM

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.

**ThePerfectHacker** · August 17th 2008, 06:31 PM

You can read this.

**Proggy** · August 17th 2008, 06:51 PM

Originally Posted by ThePerfectHacker

You can read this.

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.

**o_O** · August 17th 2008, 08:17 PM

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

Let $g$ be a primitive root of $p$ . Then, $a \equiv g^{k} \: (\text{mod } p)$ for some k since $a$ is a least residue mod p and all the powers of $g$ from 1 to $\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 $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 $a^{(p-1)/2} \equiv (g^{k})^{(p-1)/2} \equiv (g^{(p-1)/2})^{k} \equiv (-1)^{k} \equiv -1 \: ( \text{mod } p)$

**Proggy** · August 17th 2008, 08:40 PM

Originally Posted by o_O

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

Let $g$ be a primitive root of $p$ . Then, $a \equiv g^{k} \: (\text{mod } p)$ for some k since $a$ is a least residue mod p and all the powers of $g$ from 1 to $\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 $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 $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.

**kalagota** · August 17th 2008, 09:00 PM

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

**Proggy** · August 17th 2008, 09:10 PM

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.

**ThePerfectHacker** · August 17th 2008, 09:37 PM

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 $\gcd(a,p)=1$ then $a^{p-1}\equiv 1(\bmod p)$ .
Thus, $a^{p-1} - 1\equiv 0 (\bmod p)$ .
Thus, $(a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 (\bmod p)$ ---> if $p\not = 2$ .
Thus, $a^{(p-1)/2} \equiv \pm 1(\bmod p)$ .

**Proggy** · August 18th 2008, 05:08 AM

Originally Posted by ThePerfectHacker

If $\gcd(a,p)=1$ then $a^{p-1}\equiv 1(\bmod p)$ .
Thus, $a^{p-1} - 1\equiv 0 (\bmod p)$ .
Thus, $(a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1) \equiv 0 (\bmod p)$ ---> if $p\not = 2$ .
Thus, $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?

**kalagota** · August 18th 2008, 05:32 AM

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?

**Proggy** · August 18th 2008, 05:37 AM

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.

**kalagota** · August 18th 2008, 05:46 AM

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

**Proggy** · August 18th 2008, 05:54 AM

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.

Thread: [SOLVED] two questions I am stumped on

LinkBack

Thread Tools

Display

[SOLVED] two questions I am stumped on

Similar Math Help Forum Discussions

so confused :( 2 pre-calculus questions that have stumped me??

Stumped on two questions

[SOLVED] Stumped - Help get me started

[SOLVED] Stumped on this DE

Two calc questions...stumped

Search Tags