Number theory has been beautiful and oldest subject of mathematics.It's simplicity create a intrinsic interest in people.This is the reason we have many simple and beautiful conjecture and at the same time very difficult to prove.So this time we have number puzzle for you.
Let n be a natural number.Prove that
a)n has a (non-zero)multiple whose representation(base 10) contains only zeros and ones
b)2^n has a multiple whose representation contains only ones and twos.
Proof of Question 1)
ReplyDeleteproof goes as follows:
take the number n
let n=k*3^r where gcd(k,3)=1
a) We show how that a multiple of k exists
b) we show that given multiple of k which satisfies the above properties, a multiple of k*3^r exists which satisfies the same properties
Proof of a) Consider the sequence 10^i (mod k)
either 10^i =0 (mod k) => 10^i is the required multiple
OR 10^j = 1 (mod k) for some j
=> 10^j - 1 = 0 (mod k)
=> 9*(11....11) = 0 (mod k)
since gcd(k,3)=1, therefore, 11.(j ones).11 is a multiple of k which satisfies the above properties
Proof of b)
proof by induction.
We have a multiple of k which satisfies the above properties.
Given a multiple(p) of k*(3^r) , we have a multiple of k*(3^(r+1)) given by p*(10^(2t)+10^t+1)
where t = 1 + # of digits in p
Clearly the above number satisfies all the required properties.
Proved :)
simple proof:
ReplyDeletethere always exist i s.t. 10^i=1(mod n) (why?easy one)
consider 10^i+10^(2i)....+10(ni) is divisible by n.
done!!
o forgot i>0...important
ReplyDeleteproof of question 2:
ReplyDeleteproof it by pmi: 2^n has a multiple which is a no with n digits consisting of only 1's and 2's.
For n=1, it's obvious.
Let's for n=m it's true.Now let the no be Q(m).(i.e. Q(m)=k*2^m).if Q(m)/2^m is even, then Q(m+1)=2*10^m+Q(m).if Q(m)/2^m is odd,then Q(m+1)=1*10^m+Q(m).
The statement that 10^i=1(mod n) for some i - is not true.Take n=6, then 10^i=4(mod 6)or take n=8
ReplyDeletethere is no i s.t. 10^i=1(mod 8)
let 10^p(i)=r(i) (mod n). r(i)are from 0,1,2,....,(n-2),(n-1).Pair them like (0),(1,(n-1)),(2,(n-2)),...(the sum of no in the pair is n). Take {(n-1)([n/2])+1} no of different p(i)'s.Among them either there is n similar r(i)'s or a pair- the sum of that pair's no is n.(use PHP)
ReplyDeleteThen the required no is Sum over i for all such 10^p(i)'s.
ReplyDeletegud one rik.... i thought 10^i=c (mod n)and 10^j=c (mod n)for some i and j (PHP for existence). then 10^i-10^j=0(mod n). this implies 10^j(10^(i-j)-1)=0(mod n). i mistook it as 10^(i-j)=1(mod n) i forgot to consider that gcd of(10,n)=1. so that made me assume it.
ReplyDelete