Homework Help

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

user profile pic

freedomfreedom | Student, Grade 10 | (Level 1) Honors

Posted May 9, 2013 at 9:08 AM via web

dislike 2 like

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

3 Answers | Add Yours

user profile pic

mathsworkmusic | (Level 1) Educator

Posted May 11, 2013 at 4:12 PM (Answer #3)

dislike 2 like

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.

 

Top Answer

user profile pic

mathsworkmusic | (Level 1) Educator

Posted May 13, 2013 at 1:48 PM (Answer #4)

dislike 2 like

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:

user profile pic

mathsworkmusic | (Level 1) Educator

Posted May 10, 2013 at 3:51 PM (Answer #1)

dislike 1 like

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

 

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes