Wikipedia:Reference desk/Archives/Mathematics/2013 June 20

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.

June 20

limits and functions application

in a poultry farm every hen eats 2 eggs after laying 5 eggs . assuming that no hen can eat any unless after laying 5 eggs, and that every hen lays one egg every day. determine a map which gives the total number of eggs a farmer will collect after n days if he has x hens. — Preceding unsigned comment added by 41.204.186.227 (talk) 15:08, 20 June 2013 (UTC)

This is one of those two steps forward one step back, three steps forward two steps back or even two steps forward five steps back that continually come up wth the variant of having abominable cannibal hens. Anyway it sounds like an exercise, we don't answer those unless you show you have tried first. Dmcq (talk) 15:55, 20 June 2013 (UTC)

basic modular arithmetics question

I don't usually use much maths in my daily life and am forgetting it all. I am doing some revision on basic mathematics in order to refresh all that, and chose a wikibook to do that. I am on this page [1] and do not understand exercice #4:

Find all numbers x such that x² = 4 (mod 11). There are two solutions, find both.

It seems to me that there is an infinite number of solutions instead, that is an infinite number of possibilities for X.

x	x*x	(x*x)(mod 11)
-8	64	9
-7	49	5
-6	36	3
-5	25	3
-4	16	5
-3	9	9
-2	4	4
-1	1	1
0	0	0
1	1	1
2	4	4
3	9	9
4	16	5
5	25	3
6	36	3
7	49	5
8	64	9
9	81	4
10	100	1
11	121	0
12	144	1
13	169	4
14	196	9
15	225	5
16	256	3
17	289	3
18	324	5
19	361	9
20	400	4
21	441	1
...	...	...

So I am thinking that I did not understand the question. Can anyone help me see what I missed? --Lgriot (talk) 16:15, 20 June 2013 (UTC)

The exercise is badly worded. It is actually asking you to find the two congruence classes modulo 11 which satisfy x² = 4 mod 11. You are right, each congruence class actually consists of an infinite number of integers. If a = b mod 11 then a² = b² mod 11, so finding congruence classes rather than individual integers is the best you can hope to do here. Gandalf61 (talk) 16:36, 20 June 2013 (UTC)

If this was in an exam they'd expect 2 and 9 as the answers, i.e. numbers in the range 0 to 10. Very occasionally you'll see a different range like −5 to 5 used which works out nice for questions like this because the answers are then −2 and 2. Well in fact they'd expect 2 (mod 11) and 9 (mod 11) as the answer and 9 (mod 11) is exactly the same as −2 (mod 11). Dmcq (talk) 17:05, 20 June 2013 (UTC)

Thanks. For a moment I thought my brain had deteriorated really badly in the last 20 years. --Lgriot (talk) 07:58, 21 June 2013 (UTC)

Resolved

Basically, the problem can be solved in the general case, "Find all congruences X (mod p) satisfying X² = Z (mod p), given positive integers Z and p" via the somewhat naïve algorithm as follows:

Compute which of Z, Z+p, Z+2p ... are squares. You can stop at (Z/2)². Call their square roots r₁, ... , r_n.

The solutions are X = r₁, X= -r₁, ... , X = r_n, X = -r_n, and these are the only ones (if thought of as modulo classes)

If p is a prime, there will either be no solution, or there will be exactly two (so you can stop searching for squares when finding one), or exactly one if Z = 0. I don't know why but it looks solid. Proof below.

Hope that helps. - ¡Ouch! (^{hurt me} / _{more pain}) 10:18, 21 June 2013 (UTC)

Oops, found out why there's only one r if p is prime.

Say you have two, r and s, and |r+s| and |r-s| are both <p. Then r² = s² (mod p), i.e. r² - s² = a multiple of Z, but neither r+s nor r-s is.

Which means p isn't prime in that case. - ¡Ouch! (^{hurt me} / _{more pain}) 10:26, 21 June 2013 (UTC)

The Tonelli–Shanks algorithm solves the problem in polynomial time. Count Iblis (talk) 12:26, 21 June 2013 (UTC)