Intro to number theory congruence problem 1

In summary, the problem states that if n= ab, then a< n and b< n so both are factors in (n-1)!. If n= ab, then clearly a< n and b< n so both are factors in (n-1)!. However, if a=b, then this might break down the reasoning and the problem does not specify whether a=b or not or if it mattered.
  • #1
Proggy99
51
0

Homework Statement


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)

Homework Equations



The Attempt at a Solution


I know in words why a composite (ab) number does not work, but am not really sure how to prove it. Can anyone give me a jumping off point for this problem please?
 
Physics news on Phys.org
  • #2
If n= ab, then clearly a< n and b< n so both are factors in (n-1)!.
 
  • #3
HallsofIvy said:
If n= ab, then clearly a< n and b< n so both are factors in (n-1)!.

and if a|(n-1)! and b|(n-1)!, then ab|(n-1)! and since n=ab, then n|(n-1)!

Then since (n-1)! congruent 0(mod n), then (n-1)! not congruent -1(mod n)

Did I follow that through correctly?

It strikes me that if a=b, then this might break down my reasoning and the problem did not specify whether a=b or not or if it mattered. I will have to think on that a little.
 
  • #4
found the answer to my a=b or n=a^2 question. Seems that there are three possibilities to consider...when a not = b, when a=b and a is prime, when a=b and a is not prime. When a not = b and when a=b and a is not prime are easier to prove. a=b and a is prime relies on the additional information that n>4 to prove. Thanks for the help on this problem!
 
  • #5
I don't see why those have to be considered separately. If n= ab, why does it matter if a= b or not?
 
  • #6
HallsofIvy said:
I don't see why those have to be considered separately. If n= ab, why does it matter if a= b or not?


well, my professor expects us to be pretty thorough when considering all the possibilities and explaining them away. For instance:

if n=9=3*3, then ab=3*3 and (n-1)! = 1*2*3*4*5*6*7*8
The reason it still works for 3*3 is because both 3 and 2*3 occur in the problem, and in fact when n=c^2, both c and 2*c will always occur in the problem. This is because
p=n(1/2) <= (n-1)/2 for n>4, thus 2p<= n-1

I would imagine that my professor would have marked me down for not taking that into consideration, as he has done on other problems in the past. I am curious on whether you would consider it necessary to include the additional explanation or if you consider it part of the shorter explanation? Thanks again for the help HoI.
 

What is number theory congruence problem 1?

Number theory congruence problem 1 is a mathematical problem that involves finding values for variables that satisfy a given congruence equation. It is often used in number theory to study the properties of numbers and their relationships.

How do you solve number theory congruence problem 1?

To solve number theory congruence problem 1, you need to find values for the variables that satisfy the given congruence equation. This can be done by using various techniques, such as substitution, trial and error, or modular arithmetic.

What is the importance of studying number theory congruence problem 1?

Studying number theory congruence problem 1 is important because it helps us understand the fundamental properties of numbers and their relationships. It also has practical applications in fields such as cryptography and computer science.

What are some common examples of number theory congruence problem 1?

Some common examples of number theory congruence problem 1 include finding solutions to equations like 3x ≡ 4 (mod 7) or 2x + 1 ≡ 0 (mod 5). These types of equations can arise in various mathematical problems and have real-world applications as well.

How is number theory congruence problem 1 related to modular arithmetic?

Number theory congruence problem 1 is closely related to modular arithmetic, as it involves finding solutions to congruence equations using modular arithmetic concepts. Modular arithmetic is a branch of number theory that deals with arithmetic operations on congruence classes rather than individual numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
421
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
503
Replies
5
Views
315
  • Calculus and Beyond Homework Help
Replies
2
Views
983
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top