October 29th, 2011, 12:25 AM  #1 
Member Joined: Sep 2011 Posts: 97 Thanks: 0  find a difference
Suppose a1, a2, a3, ..., a'n' is a sequence of n integers none of which is divisible by n. Show that at least one of the differences ai ? aj , 1 ? i; j ? n and i != j, must be divisible by n. 
October 29th, 2011, 07:34 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: find a difference
There are n1 nonzero remainders after dividing by n, but you have n numbers. Thus, two of the numbers must have the same remainder after dividing by n by the Pigeonhole Principle. This solves the problem  why?

October 29th, 2011, 10:33 AM  #3 
Member Joined: Sep 2011 Posts: 97 Thanks: 0  Re: find a difference
erm..ok but what is the at least one diff example?

October 29th, 2011, 12:45 PM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: find a difference
If n is 2, then by assumption both numbers are odd and hence their difference is even.

October 29th, 2011, 06:42 PM  #5 
Member Joined: Sep 2011 Posts: 97 Thanks: 0  Re: find a difference
yea, that's what i thougjht too haha initially i thought the n must be greater than all the sequence of integers in order to make them not divisble by n, haha 

Tags 
difference, find 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to find the difference between angles of two complex num  ashokec  Algebra  20  April 15th, 2015 07:30 AM 
difference quotient to find f'of F(x) = (x)^(1/3)  gorgekiter  Calculus  3  October 17th, 2013 12:30 PM 
Find the Difference Quotient  jls9102  Calculus  21  September 13th, 2012 08:19 PM 
What's the difference?  student360  Computer Science  3  September 28th, 2011 12:12 PM 
Find two numbers where difference is 20 & the sum is 4  sharp  Elementary Math  7  October 30th, 2010 08:52 AM 