Show that 2^105 + 3^105 is divisible by 5, 7, 11 and 25, but not 13.

Expert Answers

An illustration of the letter 'A' in a speech bubbles

Final answer

First note that 105 can be factorised into 3 x 5 x 7 as its prime factors. Using modular arithmetic on the nested expression

`2^105 + 3^105 = ((2^3)^5)^7 + ((3^3)^5)^7`

is one way of showing whether numbers divide this expression or not.

Another is to use the...

Unlock
This Answer Now

Start your 48-hour free trial to unlock this answer and thousands more. Enjoy eNotes ad-free and cancel anytime.

Start your 48-Hour Free Trial

Final answer

First note that 105 can be factorised into 3 x 5 x 7 as its prime factors. Using modular arithmetic on the nested expression

`2^105 + 3^105 = ((2^3)^5)^7 + ((3^3)^5)^7`

is one way of showing whether numbers divide this expression or not.

Another is to use the fact that, if n is odd

`x^n + y^n = (x+y) times (...)`      (1)

where the second term on the righthand side does not concern us. So, `(x+y)` is a factor of `x^n + y^n`. The result (1) can be shown by use of the geometric series.

i) With our original expression we can let `x=2^3` and `y=3^3` . Then, `(x+y)`

divides `(x^5)^7 + (y^5)^7 = x^35 + y^35`. Now,  `x+y = 8 + 27 = 35 = 5 times 7`

so that 5 and 7 are factors of the original expression.

ii) Similarly we can let `x=2^5` and `y=3^5`. Then, `(x+y)` divides

   `(x^3)^7 + (y^3)^7 = x^21 + y^21`. Now, `x + y = 32 + 243 = 275 = 11 times 25`

so that 11 and 25 are factors of the original expression.

iii) To show that 13 is not a factor, we can use modular arithmetic on the nested expression.

`((2^3)^5)^7 + ((3^3)^5)^7`

Now, taking modulus 13, this equals

`(8^5)^7 + (1^5)^7`  (mod 13)  `= 8^7 + 1`  (mod 13)  `= 5 + 1 = 6` (mod 13).

Since the modulus base 13 of the expression does not resolve to zero, 13 is not a factor of the original expression.

5 and 7 are factors, 11 and 25 are factors, but 13 is not.

Approved by eNotes Editorial Team
An illustration of the letter 'A' in a speech bubbles

You can use modular arithmetic to show this.

Firstly, 105 = 3 x 5 x 7 using prime factorisation.

We can then write that

`2^105 + 3^105 = ((2^3)^5)^7 + ((3^3)^5)^7`

1) When taking modulus 5 of this expression, we can nest the modulus operation so that

`((2^3)^5)^7 + ((3^3)^5)^7`  (mod 5)   is equivalent to

` ``(3^5)^7 + (2^5)^7`  (mod 5) - because `8 -= 3` and `27-=2` (mod 5).

Further, this is equivalent to

`3^7 + 2^7`  (mod 5) - because `3^5 = 243 -= 3`, `2^5 = 32 -= 2`  (mod 5).

Finally, this is equivalent to (congruent to)

`2 + 3`  (mod 5)  `-= 0`  (mod 5). Therefore the expression is divisible by 5.

Alternatively, since `n= 105` is odd

`2^n + 3^n`  can be divided by `(2+3) = 5`  

(this can be shown by use of the geometric series)


2) When taking modulus 13 we again write

`2^105 + 3^105 = ((2^3)^5)^7 + ((3^3)^5)^7`   so that

`2^105 + 3^105`   (mod 13)  `-= (8^5)^7 + (12^5)^7`  (mod 13)

`-= 8^7 + 12^7 ` (mod 13)  `-= 8 + 12`   (mod 13)  `-= 7` (mod 13).

Since the modulus doesn't resolve to zero, the expression is not divisible by 13.

1) Taking modulus 5 of the expression, this resolves to zero, so the expression is divisible by 5

2) Taking modulus 13 of the expression, this does not resolve to zero, so the expression is not divisible by 13.

 

Approved by eNotes Editorial Team
An illustration of the letter 'A' in a speech bubbles

Firstly, show that `2^52` and `3^52` are congruent to 1 (mod 53).` `

According to the definition of Euler's phi function, that it equals the number of coprimes less than or equal to n,

`phi(53) = 52`

Further, Euler's theorem says that if `a` and `n` are coprime then

`a^(phi(n)) -= 1`  (mod n)

Since 53 and 2 are coprime and 53 and 3 are coprime (their only common factor is 1), `2^52 -= 1`  (mod 53).

Similarly, `3^52 -= 1`  (mod 53).

Therefore `2^105 + 3^105 = 2.2^52 2^52 + 3.3^52 3^52 -= 2(1)(1) + 3(1)(1)`

`-= 5`  (mod 53).

` `` `answer

 

Approved by eNotes Editorial Team