Probability of a Sum

Date: 08/16/2002 at 23:13:03
From: Mudit
Subject: Probability

If the integers m and n are chosen at random between 1 and 100, what 
is the probability that a number of the form 7^m + 7^n is divisible 
by 5?

Date: 08/17/2002 at 02:51:20
From: Doctor Greenie
Subject: Re: Probability

Hello, Mudit -

If you look at the congruences 7^n (mod 5) for n = 1 to 100, you will 
find that

  7^n == 2 (mod 5) for integers n of the form 4k+1;
  7^n == 4 (mod 5) for integers n of the form 4k+2;
  7^n == 3 (mod 5) for integers n of the form 4k+3;
  7^n == 1 (mod 5) for integers n of the form 4k

Of the numbers from 1 to 100, exactly 1/4 of them are of the form 
4k+1, exactly 1/4 of them are of the form 4k+2, exactly 1/4 of them 
are of the form 4k+3, and exactly 1/4 of them are of the form 4k.  
Once you choose one of the numbers between 1 and 100 for m, the 
choice for n, to make the sum 7^m + 7^n divisible by 5, is limited to 
the numbers in exactly one of these groups: 

  If you choose m so that 7^m == 1 (mod 5), then to have 7^m + 7^n
  divisible by 5, you need to choose n so that 7^n == 4 (mod 5).

  If you choose m so that 7^m == 2 (mod 5), then to have 7^m + 7^n
  divisible by 5, you need to choose n so that 7^n == 3 (mod 5).

  If you choose m so that 7^m == 3 (mod 5), then to have 7^m + 7^n
  divisible by 5, you need to choose n so that 7^n == 2 (mod 5).

  If you choose m so that 7^m == 4 (mod 5), then to have 7^m + 7^n
  divisible by 5, you need to choose n so that 7^n == 1 (mod 5).

Therefore, no matter what number you choose for the first of your two 
choices for m or n, the probability is 1/4 that the number you choose 
for the second one will make your sum divisible by 5.

The probability that two numbers m and n chosen at random from the 
numbers 1 to 100 will make the sum 7^m + 7^n divisible by 5 is 1/4.

I hope this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/