My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 13th, 2015, 04:46 AM   #1
Member
 
Rishabh's Avatar
 
Joined: May 2014
From: India

Posts: 87
Thanks: 5

Math Focus: Abstract maths!
Proof regarding divisibility of factorial by composite numbers.

If N is a composite number greater than 4, prove that:
$(N - 1)! \equiv 0(mod N)$
Rishabh is offline  
 
May 13th, 2015, 04:50 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Let N = ab with a,b coprime and greater than 1. Then since a and b are both less than N-1, both divide (N-1)! and hence ab divides (N-1)!, as desired.

All that's left is for you to handle the case of powers of primes.
CRGreathouse is offline  
May 13th, 2015, 05:16 AM   #3
Member
 
Rishabh's Avatar
 
Joined: May 2014
From: India

Posts: 87
Thanks: 5

Math Focus: Abstract maths!
Quote:
Originally Posted by CRGreathouse View Post
All that's left is for you to handle the case of powers of primes.
That's exactly where I am having a problem.
Rishabh is offline  
May 13th, 2015, 05:50 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Rishabh View Post
That's exactly where I am having a problem.
It's a pity you didn't mention that, or I would have worked out that case instead of the other. Why don't you show me the work you've done so far and I'll see if I can help you along?
CRGreathouse is offline  
May 13th, 2015, 11:36 PM   #5
Member
 
Joined: Jul 2014
From: israel

Posts: 76
Thanks: 3

this will help you out

Wilson's theorem - Wikipedia, the free encyclopedia


Wilson's theorem states that a natural number n > 1 is a prime number if and only if

(N−1)!≡-1(mod N)

Lagrange gave the first proof in 1771

please also check the "Composite modulus" section

...

Last edited by isaac; May 13th, 2015 at 11:40 PM.
isaac is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
composite, divisibility, factorial, numbers, proof



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
prime numbers and composite numbers shaimaa saif Algebra 10 November 17th, 2015 08:02 AM
Composite numbers prime-like mobel Number Theory 24 October 30th, 2014 09:18 AM
Some rules about composite numbers Tylerman Number Theory 26 April 17th, 2012 09:43 PM
Composite numbers among a formula butabi Number Theory 2 October 12th, 2010 12:26 PM
Factorial for complex numbers? 3hlang Number Theory 1 June 5th, 2009 11:57 AM





Copyright © 2019 My Math Forum. All rights reserved.