Google

A mathematical experiment

Give feedback

Sometimes a mathematical experiment can be of use and help one to get an idea of how to get closer to a mathematical proof.

The table at the bottom of this page (open table in new window) illustrates solutions to the following problem:

For each positive integer n and odd k > 1, find the largest number N such that 2N divides kn - 1.

In the table, n is the columns and k is the rows, and the resolved N is the value in the cell.

This has been calculated without any shortcut formula, so the cells without value could not be calculated since the intermediate results were too big.

I can see in the table that all odd columns are the same. And I can see that the value for the k row in an odd column is found by first subtracting 1 from k, and then check how many times you can divide that by 2.

Let's call that the base formula.

I also see in the table that for an even n column the value of a cell is obtained by taking the value on the same row of an odd column (for example the odd column to the left of the even column in question) and adding that to the value of the next row in the odd column. Then subtract 1 from that and add the number of times n can be divided by 2.

One can translate the above information into two general formulas that clearly seem to be the solution to the problem.

Using the notation a # b to mean the number of times you can divide a by b, the general formula for the problem seems to be, for odd columns:

N = (k - 1) # 2

And for even columns:

N = [(k - 1) # 2] + [(k + 1) # 2] + [n # 2] - 1

Now, either   (k - 1) # 2   or   (k + 1) # 2   will be 1. And it is easy to see which one it is, so if you eliminate that one the formula becomes more simple. So if we denote the row that does not become 1 by j then the formula becomes:

N = [(j - 1) # 2] + [n # 2]

And it seems that this "backdoor" to the solution, obtained through some experimental math, could help one to understand the problem and find a way to reason to prove the solution mathematically. If you do, then plesae let me know through the feedback link above.

Anyway, let's use our experimental results to calculate the value for a coordinate in the table. Let's take for example the 3234 column and the 9783 row.

We first calculate the value for the 9783 row and the 9783+2 row of an odd column according to the base formula. We start with 9783. Subtract 1 and we get 9782. How many times can that be divided by 2? 1 time. Ok, we now take the next row, namely the 9783+2 row. 9783+2=9785. Subtract 1 and we get 9784. How many times can that be divided by 2? 3 times. Now we will apply this 1 and 3 to our rule for getting the value of the 9783 row of the even 3234 column. We first add 1 and 3 and get 4. We subtract 1 and get 3. Then we check how many times we can divide 3234 by 2. We can divide it only 1 time. So we add that 1 to the 3 that we have and we get 4. So the value for the 3234 column and the 9783 row clearly seems to be 4.

In other words, the largest number N such that 2N divides 97833234 - 1 clearly seems to be 4.

Let's try with even greater numbers. The largest number N such that 2N divides 1478635671537893496 - 1 clearly seems to be 7.

We can now use our formulas to complete the table so that all cells are filled in, even those cells which we had to leave emtpy in the first table shown below, because the intermediate results were to big. Open completed table in a new window.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
3 1 3 1 4 1 3 1 5 1 3 1 4 1 3 1 6 1 3 1
5 2 3 2 4 2 3 2 5 2 3 2 4 2            
7 1 4 1 5 1 4 1 6 1 4 1                
9 3 4 3 5 3 4 3 6 3                    
11 1 3 1 4 1 3 1 5                      
13 2 3 2 4 2 3 2 5                      
15 1 5 1 6 1 5 1                        
17 4 5 4 6 4 5 4                        
19 1 3 1 4 1 3 1                        
21 2 3 2 4 2 3 2                        
23 1 4 1 5 1 4                          
25 3 4 3 5 3 4                          
27 1 3 1 4 1 3                          
29 2 3 2 4 2 3                          
31 1 6 1 7 1 6                          
33 5 6 5 7 5 6                          
35 1 3 1 4 1 3                          
37 2 3 2 4 2                            
39 1 4 1 5 1                            
41 3 4 3 5 3                            
43 1 3 1 4 1                            
45 2 3 2 4 2                            
47 1 5 1 6 1                            
49 4 5 4 6 4                            
51 1 3 1 4 1                            
53 2 3 2 4 2                            
55 1 4 1 5 1                            
57 3 4 3 5 3                            
59 1 3 1 4 1                            
61 2 3 2 4 2                            
63 1 7 1 8 1                            
65 6 7 6 8 6                            
67 1 3 1 4 1                            
69 2 3 2 4 2                            
71 1 4 1 5 1                            
73 3 4 3 5 3                            
75 1 3 1 4                              
77 2 3 2 4                              
79 1 5 1 6                              
81 4 5 4 6                              
83 1 3 1 4                              
85 2 3 2 4                              
87 1 4 1 5                              
89 3 4 3 5                              
91 1 3 1 4                              
93 2 3 2 4                              
95 1 6 1 7                              
97 5 6 5 7                              
99 1 3 1 4                              
101 2 3 2 4                              
103 1 4 1 5                              
105 3 4 3 5                              
107 1 3 1 4                              
109 2 3 2 4                              
111 1 5 1 6                              
113 4 5 4 6                              
115 1 3 1 4                              
117 2 3 2 4                              
119 1 4 1 5                              
121 3 4 3 5                              
123 1 3 1 4                              
125 2 3 2 4                              
127 1 8 1 9                              
129 7 8 7 9                              
131 1 3 1 4                              
133 2 3 2 4                              
135 1 4 1 5                              
137 3 4 3 5                              
139 1 3 1 4                              
141 2 3 2 4                              
143 1 5 1 6                              
145 4 5 4 6                              
147 1 3 1 4                              
149 2 3 2 4                              
151 1 4 1 5                              
153 3 4 3 5                              
155 1 3 1 4                              
157 2 3 2 4                              
159 1 6 1 7                              
161 5 6 5 7                              
163 1 3 1 4                              
165 2 3 2 4                              
167 1 4 1 5                              
169 3 4 3 5                              
171 1 3 1 4                              
173 2 3 2 4                              
175 1 5 1 6                              
177 4 5 4 6                              
179 1 3 1 4                              
181 2 3 2 4                              
183 1 4 1 5                              
185 3 4 3 5                              
187 1 3 1 4                              
189 2 3 2 4                              
191 1 7 1 8                              
193 6 7 6 8                              
195 1 3 1 4                              
197 2 3 2 4                              
199 1 4 1 5                              
201 3 4 3 5                              
203 1 3 1 4                              
205 2 3 2 4                              
207 1 5 1 6                              
209 4 5 4 6                              
211 1 3 1 4                              
213 2 3 2 4                              
215 1 4 1 5                              
217 3 4 3                                
219 1 3 1                                
221 2 3 2                                
223 1 6 1                                
225 5 6 5                                
227 1 3 1                                
229 2 3 2                                
231 1 4 1                                
233 3 4 3                                
235 1 3 1                                
237 2 3 2                                
239 1 5 1                                
241 4 5 4                                
243 1 3 1                                
245 2 3 2                                
247 1 4 1                                
249 3 4 3                                
251 1 3 1                                
253 2 3 2                                
255 1 9 1                                
257 8 9 8                                
259 1 3 1                                
261 2 3 2                                
263 1 4 1                                
265 3 4 3                                
267 1 3 1                                
269 2 3 2                                
271 1 5 1                                
273 4 5 4                                
275 1 3 1                                
277 2 3 2                                
279 1 4 1                                
281 3 4 3                                
283 1 3 1                                
285 2 3 2                                
287 1 6 1                                
289 5 6 5                                
291 1 3 1                                
293 2 3 2                                
295 1 4 1                                
297 3 4 3                                
299 1 3 1                                
301 2 3 2                                
303 1 5 1                                
305 4 5 4                                
307 1 3 1                                
309 2 3 2                                
311 1 4 1                                
313 3 4 3                                
315 1 3 1                                
317 2 3 2                                
319 1 7 1                                
321 6 7 6                                
323 1 3 1                                
325 2 3 2                                
327 1 4 1                                
329 3 4 3                                
331 1 3 1                                
333 2 3 2                                
335 1 5 1                                
337 4 5 4                                
339 1 3 1                                
341 2 3 2                                
343 1 4 1                                
345 3 4 3                                
347 1 3 1                                
349 2 3 2                                
351 1 6 1                                
353 5 6 5                                
355 1 3 1                                
357 2 3 2                                
359 1 4 1                                
361 3 4 3                                
363 1 3 1                                
365 2 3 2                                
367 1 5 1                                
369 4 5 4                                
371 1 3 1                                
373 2 3 2                                
375 1 4 1                                
377 3 4 3                                
379 1 3 1                                
381 2 3 2                                
383 1 8 1                                
385 7 8 7                                
387 1 3 1                                
389 2 3 2                                
391 1 4 1                                
393 3 4 3                                
395 1 3 1                                
397 2 3 2                                
399 1 5 1