How many numbers from 7, 13, 14, 21, 26, 39 and 91 divide (6912 − 3812)? Euler, Fermat and Wilson’s Theorems

Question of the Day (11-Apr-12)

 How many numbers from 7, 13, 14, 21, 26, 39 and 91 divide (69¹² − 38¹²)?

Let N = 69¹² − 38¹² 

∴ N = (69¹² – 1) – (38¹² – 1)

       

        = (69^{(13 – 1)} – 1) – (38^{(13 – 1)} – 1)

By Fermat’s theorem, N is divisible by 13.

Also,

N = (69⁶ – 1)(69⁶ + 1) – (38⁶ – 1)(38⁶ + 1)

    = (69^{(7 – 1)} – 1)(69⁶ + 1) – (38^{(7 – 1)} – 1)(38⁶ + 1)

Again by Fermat’s theorem, N is divisible by 7.

So N is divisible by 7, 13 and 91.

N is odd. So it cannot be divisible by 14 and 26.

69¹² is divisible by 3 but 38¹² is not, so N is not divisible by 3 and hence not divisible by 21 and 39.

----

 Euler, Fermat and Wilson’s Theorems

In previous posts, we have already discussed how to find out the last two digits and basic ideas of remainders. However, there are theorems by Euler, Fermat & Wilson that make calculation of remainders easier. Let’s have a look at them.

Funda 1 – Euler:

Number of numbers which are less than N = a^p * b^q * c^r and co-prime to it are,

If M and N are co-prime, that is if HCF(M,N) = 1,

A very common mistake that students tend to make while using the Euler’s Theorem to solve questions is that they forget that M and N have to be co-prime to each other. There is another set of students (such as I in college) who don’t even understand what to do with the theorem or how to use it to solve questions. Let us look at couple of examples in which Euler’s Theorem is used.

Note: ∅(N) is also known as Euler’s Totient Function.

Example,

Funda 2 – Fermat’s Little Theorem

If  ‘p’ is a prime number and ‘a’ and ‘p’ are co-primes,

If you notice, the three statements above are saying exactly the same thing but in a different way. It is important to keep all three in mind because sometimes it becomes a little difficult to analyze which interpretation of Fermat’s little theorem is to be used.

A simple illustration of this is,

We can check it by noticing that

10⁷ = 10000000 = 9999990+10 = 142857 ∗ 7 + 10

Another way that you can remember Fermat’s Little Theorem (I am not joking, that is the official name –check this) is by observing that it is but a special case of Euler’s Theorem where ‘N’ is a prime number.

Because, if ‘N’ is prime then ∅(N) or the Euler’s Totient Function will always be (N-1).

Funda 3: Wilson

Sometimes people find the history behind Wilson’s theorem to be more interesting than the theorem itself. Actually, the theorem was already known to the great Muslim polymath Alhazen approximately seven and a half centuries before John Wilson was born. Alhazen, being the great scientist that he was, never bothered to prove it and was instead regulating floods in the river Nile. After being ordered by Al-Hakim bi-Amr Allah, the sixth ruler of the Fatimid caliphate to carry out this operation, Alhazen quickly perceived the impossibility of what he was attempting to do, and retired from engineering. Fearing for his life, he feigned madness and was placed under house arrest, during and after which he devoted himself to his scientific work until his death.

The English mathematician, John Wilson, stated it in the 18^th century but he could not prove it either. Actually Wilson was a student of Edward Waring, who announced the theorem in 1770. None of them could prove it. Lagrange proved it in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.

I think I will end the history lesson here and resume the mathematics.

For a prime number ‘p’,

Another related result to the Wilson Theorem is,

Example,

Note: I have checked the related results for primes up to 120 and found it to be valid. I could not find a proof for it that I could understand. Do note that the key part of the previous sentence is not ‘find a proof for it’ but ‘that I could understand’. May be one of you can help me out in comments

Points P and Q lie on sides AC and BC of a ΔABC respectively with AB = 20 cm, BC = 12 cm and AC = 10 cm. PY is parallel to AQ and QX is parallel to BP such that Y lies on BC and X on AC. If A(ΔCXY) = 7.2 sq. cm, what is ℓ(XY)?

 

Points P and Q lie on sides AC and BC of a ΔABC respectively with AB = 20 cm, BC = 12 cm and AC = 10 cm. PY is parallel to AQ and QX is parallel to BP such that Y lies on BC and X on AC. If A(ΔCXY) = 7.2 sq. cm, what is ℓ(XY)?

 
Question of the Day (09-Apr-12)


As AQ || PY, we can see that

ΔCPY ~ ΔCAQ

 

As BP || QX, we can see that

ΔCPB ~ ΔCXQ

 

From (i) and (ii),

CP × CQ = CY × CA = CB × CX

 

As a line parallel to the base of the triangle divides the other two sides in equal ratios, we can say that XY || AB.

∴ ΔCXY ~ ΔCAB

 

Semiperimeter, s of ΔABC = (20 + 10 + 12)/2 = 21 cm

 

∴ From (iii),

(XY)² = 7.2 × 400/45 = 64

∴ XY = 8 cm

What is the number of positive solutions to (x1000 + 1)(1 + x2 + x4 + … + x998) = 1000x999?

What is the number of positive solutions to (x1000 + 1)(1 + x2 + x4 + … + x998) = 1000x999?

Question of the Day (30-Mar-12) option 2...for x=1. (x^1000 + 1)(1 + x^2 + x^4 + . + x^998) = 1000.x^999 -----(1) let S=1 + x^2 + x^4 + . + x^998. hence,S*x^2=x^2 + x^4 + . + x^1000. Now, S.x^2 - S=x^1000 - 1. means S(x^2 - 1)=x^1000 - 1. hence,S=(x^1000 - 1)/(x^2 - 1). Now, Equation (1) will become, (x^1000 + 1)*(x^1000 - 1)/(x^2 - 1)=1000*x^999. ===> (x^2000 - 1)=(x^2 - 1)(1000*x^999) ===> x^1001*x^999 -1 = 1000*x^1001 - 1000*x^999. ===> x^1001*x^999 - 1000*x^1001 =1 - 1000*x^999. ===> x^1001(x^999 - 1000)=(1 - 1000*x^999)------(2) in equation (2),we can see for all +ve values of X greater than 1, (x^999 - 1000) this will give +ve value. x^1001 will be +ve.Hence,x^1001(x^999 - 1000) will be +ve. But,for same x values (1 - 1000*x^999) will give -ve values.So,for x>1,above L.H.S won't be equal to R.H.S. Similarly,for all -ve values of x less than -1,x^1001(x^999 - 1000) will be far more than (1 - 1000*x^999). Hence,L.H.S won't will be equal to R.H.S for x less than -1. NOw,for x=1,both L.H.S will be same and equal -999. for x=-1,both L.H.S will be same and equal to 1001. Hence,solution for the equation will be x=1 and -1. But,question is asking us for only +ve solution,hence x can be only 1 not -1.

How many seven-digit numbers divisible by 11 have the sum of their digits equal to 59?

How many seven-digit numbers divisible by 11 have the sum of their digits equal to 59?

ANS- 40
Let abcdefg be a seven digit number.
Then a + b + c + d + e + f + g = 59         …(i)

Now, for the number to be divisible by 11,

|(a + c + e + g) – (b + d + f)| = 0 or 11 or 22 …

If |(a + c + e + g) – (b + d + f)| = 0, then from (i),

2(a + c + e + g) = 59, which is not possible.

Similarly, |(a + c + e + g) – (b + d + f)| cannot have any even value.

If |(a + c + e + g) – (b + d + f)| = 33, then from (i),

(a + c + e + g) = 92/2 = 46, which is not possible as the maximum sum of 4 digits is 9 × 4 = 36. Clearly, (b + d + f) = 46 is also not possible.

Similarly, |(a + c + e + g) – (b + d + f)| cannot have any value greater than 33 either.

∴ |(a + c + e + g) – (b + d + f)| = 11      …(ii)

From (i) and (ii), (a + c + e + g) = 35 or (b + d + f) = 35.

The second case is not possible as the maximum sum of 3 digits can be 27.

∴ (a + c + e + g) = 35 and (b + d + f) = 24

Now consider

a + c + e + g = 35

The maximum sum of a, b, c and d is 36 when a = c = e = g = 9

But our sum is 35. So we assign (−1) among the four variables. This can happen in 4 ways. Thus there are only 4 solutions to this equation, namely, (9, 9, 9, 8), (9, 9, 8, 9), (9, 8, 9, 9) and (8, 9, 9, 9).

Now consider

b + d + f = 24

The maximum sum of b, d and f is 27, when b = d = f = 9

But our sum is 24. So we distribute (−3) among the 3 variables.

Thus (b’ – j) + (d’ – k) + (f’ – l) = 24, where j + k + l = 3

The equation j + k + l has (3 + 3 – 1)C(3 – 1) = 5C2 = 10 solutions.

Thus there are 4 × 10 = 40 numbers that satisfy our conditions.

Question of the Day (03-Apr-12) Views : 1392 Rated 4.7 by 3 Users   Let f(n, k) denote the number of ways in which the set S = {1, 2, 3, 4,… n} can be partitioned into k non-empty subsets. For example, f(3, 2) = 3 since we can partition {1, 2, 3} into 2 subsets in 3 ways: {1, 2}{3}; {1, 3}{2} and {2, 3}{1}.  Similarly f(4, 2) = 7 since there are 7 ways to partition {1, 2, 3, 4} into 2 sets: {1, 2}{3, 4}; {1, 3}{2, 4}; {1, 4}{2, 3}; {1, 2, 3}{4}; {1, 2, 4}{3}; {1, 3, 4}{2}; {1}{2, 3, 4}. We assume that f(0, 0) = 1. What is the value of f(7, 4) if f(6, 3) = 90 and f(6, 4) = 65? -----------------------

 Consider two kinds of ways in which {1, 2, 3,…, 7} can be divided into 4 subsets:

A. {7} is one of the four sets and there are three other sets. E.g. {1}{5, 3, 2}{4, 6}{7}

B. 7 occurs with some other number(s) in one of the sets e.g. {1, 6}{4}{3, 5}{2, 7}

Now, the number of ways of type A are equal to the number of ways of dividing {1, 2, 3,…, 6} into 3 subsets.

The number of ways of type B are equal to the number of ways of dividing {1, 2, 3,…, 6} into 4 subsets multiplied by 4 (since we could ‘attach’ 7 to any of the four sets).

∴ f(7, 4) = f(6, 3) + 4f(6, 4)

In general, f(n, k) follows the recursion f(n, k) = k ×  f(n– 1, k) + f(n – 1, k – 1)

∴ f(7, 4) = 90 + 4 × 65 = 350

http://www.indiaagainstcorruption.org/lokpal.html

http://www.pagalguy.com/forum/career-discussions/60071-probationary-officers-test-aspirants-nov-530.html#post2464102

Cabinet has cleared the FDI policy that allows multi brand retail in India, and companies like Walmart and Carrefour can now partner with an Indian company and sell to consumers .

The persistently high inflation and the current Euro mess must have a lot to do with the timing of this decision but the decision itself was a long time pending.

Everyone knows stories of the food grain that rots in India’s warehouses and though India is the second largest producer of fruits and vegetables in the world with a production of 180 million tons - it has only 5,386 stand alone cold storage units with a capacity of 23.6 million tons – 80% of which are used just for potatoes!

Back to the policy, it stipulates the following key things:

• The foreign equity player will own up to 51% of the stake through the government approval route.
• The policy will be rolled out to only cities with a population of more than 1 million people and there are currently only 53 such cities in India – out of a total of 7935 cities.
• A minimum investment of a $100 million is required and half of that should be in backend infrastructure like cold chains, transportation etc.
• They have to source a minimum of 30% from Indian micro and small industry having capital investment of less than a million dollars.

India is not the first one to do this, and what it has done is not unique either. Many developing countries have much more liberal policies than India. These countries include China, Brazil, Mexico, Thailand, Russia, Singapore, Argentina and Indonesia among others.

In fact China started out in much the same way as India allowing 51% foreign equity and confining them to large cities. They only removed these restrictions in 2005 after having them in place for more than 10 years. They gave the domestic players enough to time to get up to speed with the western model and then allowed free competition.

It has turned out quite well for them as most of the top 10 retail companies in China are local and not foreign. These were the top 10 Chinese retailers in 2010.

1. Suning Appliance Group
2. Gome Electrical Appliances Co., Ltd.
3. Bailian Group Co., Ltd.
4. Dashang Group Co., Ltd.
5. Vanguard Co., Ltd.
6. RT-MART International Co., Ltd.
7. Carrefour S.A. (China)
8. Anhui Huishang Group Co., Ltd.
9. Wal-Mart Stores, Inc.  (China)
10. Chongqing General Trading (Group) Co., Ltd

This clearly shows that Chinese companies didn’t let much bigger foreign players compete them out of the market, and the Indian experience shows the same thing in areas like telecom where foreign and local players co-exist.

What’s even more fascinating is that the number of Chinese equivalent of kirana stores rose from 1.9 million to 2.5 million after the liberalization of its retail sector!

This is because of economic growth of course and also because big players don’t have a magic wand that they can use to ouster other smaller players as soon as they enter any market. Many of their strengths in their home countries are based on factors that are totally absent in other countries. Wal-Mart is able to drive costs down because of its incredible logistics and supply chains which are absent in India as they were absent in China.

Then there is the question of physical infrastructure like roads and ports that are not to the same level as they are in the US and they simply won’t have the kind of scale that they have in the US to negotiate and bargain with the suppliers and drive down the cost.

Local knowledge is also an important thing and I found an interesting example of that in this Harvard article written in 2005.

Here is the example:

In the grocery section of its stores, Wal-Mart originally offered meat and seafood American-style, in plastic-wrapped, freshness-dated containers. To Chinese consumers, however, “fresh” means that you can pick it out yourself and watch it wriggle – so they took a pass.

Big companies can’t set up shop and drive out smaller players overnight – they have advantages in some areas but that doesn’t mean the smaller players are completely at their mercy.

Don’t underestimate the innovation and resolve of Indian entrepreneurs and companies that compete with much larger companies globally. IBM earns more in a quarter than the top 3 Indian IT companies earn in a year, and yet they give IBM a run for its money in many contracts

Even now, organized domestic retail players are present in the market, but mom and pop stores are not going out of business because of them. I think this will hold true in the future as well, and allowing FDI will be a big net positive for everyone.

Wal-Mart is going to invest $756 million in Brazil and hire 7,000 people this year, and India can expect similar type of investments from these big players. And this is not hot money that goes out of the stock market and leaves it reeling every time someone in Europe sneezes. FDI flows are a lot more stable than FII flows and that’s a good thing.

Getting efficient supply chains and eliminating middle men is good for both consumers and farmers as this will give both parties a better price.

Getting more of the retail sector under the organized sector is also good because it leads to more employment and also of a better quality.

Anyone who remembers the time it used to take to get a phone connection or the big hassle it was to chase after the telephone guy to fix the phone knows how great competition is and I don’t think anyone is really questioning whether this policy is good for customers or not.

My view is that this will be good not only for the customers but for everyone involved, and that the current policy allows us to test that view without a lot of risk.

The potential upside is immense, and the downside is limited – I think FDI in multi brand retail is great for everyone, and I hope this great first step doesn’t get derailed.