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

### 3 Answers | Add Yours

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.**

**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.**

**Sources:**

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**