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