Wikipedia:Reference desk/Archives/Mathematics/2013 November 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 27

How can I solve this without actually performing this long calculation?

10¹⁵ + 12¹⁵ is divisible by which of the following numbers?
a)15 b)27 c)22 d)none of these
This question was asked in a competitive exam earlier this month. I know the answer is 22, but I don't know how to solve this using some trick when you have very limited time. Please show me the way and if you know any related article to my question, please post the link. Scientist456 (talk) 04:23, 27 November 2013 (UTC)

Since 12 is divisible by 3 and 10 isn't, that means 10¹⁵ + 12¹⁵ is not divisible by 3. Since 3 divides both 15 and 27, neither of these can divide 10¹⁵ + 12¹⁵; thus, you have one choice left, 22.Phoenixia1177 (talk) 05:07, 27 November 2013 (UTC)

Next, 22 = 2×11, certainly both 10 and 12 is divisible by 2, so you only need to check if the number given is divisible by 11. Number 11 is not divisible by 2, so you can get rid of powers of 2: (10¹⁵ + 12¹⁵) / 2¹⁵ = 5¹⁵ + 6¹⁵.... (hth) --CiaPan (talk) 07:08, 27 November 2013 (UTC)

$a^{2n+1}+b^{2n+1}$ is always divisible through (a+b). In this particular case (n = 7), 10¹⁵ + 12¹⁵ is divisible through 10+12 = 22. — 79.113.210.39 (talk) 07:14, 27 November 2013 (UTC)

In a more general case, you can drop multiples of any divisor d to decide if a large number is a multiple of d, or what the remainder is, at least as long as you only add, subtract, and multiply integers. The remainder of x / y is usually called x mod y.

Say you want to find 10¹⁵ mod 11; your d is 11 and you can compute 10⁵ mod 11 first. 99990 is a multiple of 11, so the remainder is 10. Now,

10¹⁵ mod 11 = (10⁵)³ mod 11 = (10⁵ mod 11)³ mod 11 = 10³ mod 11.

Because 990 is a multiple of 11, this is 10.

This works because (11x+r)³ = 11³x³ + 3 (11²x² r) + 3 (11x r²) + r³;

all terms but the last are multiples of 11 and thus irrelevant to the remainder calculation.

- ¡Ouch! (^{hurt me} / _{more pain}) 08:49, 27 November 2013 (UTC)

Really, this (above) is the best way of answering my question; I got my answer. User 79.113.210.39 suggested a very nice formula to solve the question when the powers are odd. A further extension to my question can be: what if the powers were even (instead of odd)? Please, bear me this time. Scientist456 (talk) 12:18, 27 November 2013 (UTC)

If your exponent is even, but NOT a power of two, then bring out its odd part: i.e., $a^{2k}+b^{2k}=(a^{2})^{k}+(b^{2})^{k}=A^{k}+B^{k}=...$. Repeat until k becomes odd; E.g. $a^{10}+b^{10}=(a^{2})^{5}+(b^{2})^{5}=A^{5}+B^{5}=(A+B)(A^{4}-A^{3}B+A^{2}B^{2}-AB^{3}+B^{4})$ — 79.113.219.169 (talk) 08:28, 2 December 2013 (UTC)

Mod 11, you have that 10 = -1 and 12 = 1, so 10^n + 12^n = (-1)^n + 1^n = 0 if n is odd and 2 if n is even. Mod 2, both 10 and 12 are equal to 0. Count Iblis (talk) 17:43, 27 November 2013 (UTC)

Graph theory terminology

What are the names/notations for the following two operations on a graph. I need to be able to distinguish between them in text.

1. The removal of a node and all the edges connected to it from a graph.
2. The removal of a node and all the edges connected to it together with the introduction of an edge between each pair of nodes previously connected via the removed node.

Thank you. — Preceding unsigned comment added by 109.158.148.43 (talk) 22:40, 27 November 2013 (UTC)

The first operation is sometimes called node thinning, as in [1]. I don't know a name for the second process, but after node thinning, it would create a clique among all the nodes that were next-nearest neighbors through the removed node. --Mark viking (talk) 23:14, 27 November 2013 (UTC)

...so you might describe (2) as 'building a clique of neighbours of the node being removed'.
For (1) just say you remove a node. A graph's edge is defined as pair of nodes (ordered or not), so removing a node implicitly cancels all edges connected to it. --CiaPan (talk) 06:15, 28 November 2013 (UTC)