OK, this is something I had programmed into my calculator:

1. Input "Q"
2. A, B and N all equal 1
3. A+B -> A
4. A+B -> B
5. A mod Q -> A
6. B mod Q -> B
7. N+1 -> N
8. If (A+B> 1) Then goto step 3
9. Else print N

It's a short program, but when I plugged different numbers into it, I got a weird set of results.

It's to do with using fibonacci in clock arithmatic, basically acknowledging that it will repeat under any base, and seeing how the period of repetition changes with regard to the base.
I've started to poke my way through it, and have found a number of 'rules', but have no idea how to prove them, or how to finish off the set.

Any ideas?

This sounds very interesting, but what are your results? And what are the rules you found?

OK,Results from 3 to 100:
3....4
4 ....3
5.... 10
6.... 12
7.... 8
8.... 6
9.... 12
10... 30
11... 5
12... 12
13... 14
14... 24
15... 20
16... 12
17... 18
18... 12
19... 9
20... 30
21... 8
22... 15
23... 24
24... 12
25... 50
26... 42
27... 36
28... 24
29... 7
30... 60
31... 15
32... 24
33... 20
34... 18
35... 40
36... 12
37... 38
38... 9
39... 28
40... 30
41... 20
42... 24
43... 44
44... 15
45... 60
46... 24
47... 16
48... 12
49... 56
50... 150
51... 36
52... 42
53... 54
54... 36
55... 10
56... 24
57... 36
58... 21
59... 29
60... 60
61... 30
62... 15
63... 24
64... 48
65... 70
66... 60
67... 68
68... 18
69... 24
70... 120
71... 35
72... 12
73... 74
74... 114
75... 100
76... 9
77... 40
78...84
79... 39
80... 60
81... 108
82... 60
83... 84
84... 24
85... 90
86... 132
87... 28
88... 30
89... 22
90... 60
91... 56
92... 24
93... 60
94... 48
95... 90
96... 24
97... 98
98... 168
99... 60
100.. 150

Basic rule for calculating a number:

1.Find the prime roots of your number, eg
735 = 3*5*7*7
2.Get the number on the right for each number, eg
3 -> 4
5 -> 10
7 -> 8
3. Find the lowest common multiple of these numbers, eg
LCM of 4, 8 and 10 = 40

4. But 7 appears 2ce in the original, so multiply this last number by 7, eg
40*7 = 280

5. So this is the number, putting 735 in will generate '280'.

These all seem very arbitrary steps, but it always seems to work. Any proofs or counterexamples?
btw, 2 is a weird one - I'll explain later.

William - are you sure about your program? It seems to me that you test on the pair (F_2N-1 ,F_2N ) and then (F_2N+1 ,F_2N+2 ), with the omission of (F_2N ,F_2N+1 ) for all positive integer N that you labelled.

Kerwin

Yes, you're right - 2 major reasons I don't use it are 1/because it would be slightly more effort to program, and 2/because looking at the lists, it always seems to repeat like that. If I'm wrong, then it would just halve some or all values, but that's another interesting facet to think about.

I think at least I can see why you only have to check every other pair.

If I understand correctly, we have

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3

Etc. And we want the lowest positive integer p where:

F(p) = 0
F(p+1) = 1

(where we are working to modulo q)

Well let's go from the start and the end at the same time. (Working to modulo q all the time.)

F(0) = 0, F(p) = 0
F(1) = 1, F(p-1) = 1
F(2) = 1, F(p-2) = -1
F(3) = 2, F(p-3) = 2
F(4) = 3, F(p-4) = -3
F(5) = 5, F(p-5) = 5

(using the Fibonacci recurrence relationships).

If we go another p-6 steps down:

F(p-1) = 1, F(1) = (-1)^(p-6) * F(p-1)

But we know F(1) = F(p-1) = 1. So:

(-1)^(p-6) = 1 (mod q)

Therefore p is even as long as q is bigger than 2, so you only have to check every other pair of numbers. For q = 2 it is also true, so that means the program will not miss any out.

The method of working backwards as well as forwards may give insight into solving the general problem; I'm not sure.

Hope that's correct,

Michael

Whoops - I said it worked for q = 2 didn't I? Well it doesn't because if you're working modulo 2 it starts:

0
1
1
0
1
1
0
1
1
etc

which recurs after 3 numbers (which is odd). But anyway, you didn't list q = 2, so it doesn't matter.

Michael

Yeah. The reason I didn't list Q=2 is because it is weird. First of all, doing it your way, Michael gives n=1.5, the only noninteger value I can see. Secondly, after I sussed out the 'rules' a little, I discovered one thing.
If you take a prime number Q1(eg 3), you get a result N1(4). Squaring the number Q1*Q1=Q2(9) gives you the result N2(12). This is Q1*N1. I don't know why. Cubing the number Q1*Q1*Q1=Q3(27) gives you N3(36). This is Q1*Q1*N1.
However, this result only (and always) seems to work on prime numbers.
The exception for this seems to be Q=2, Q=4. I think it seems to work if you treat both 2 and 4 as prime numbers, and if it can be divided by 4, do so otherwise use 2 - if you know what I mean.

Well we do know for certain, that 1.5 is the only non-integer that can ever possibly come up. As proved above for Q ³ 3 (in my first message), the number of steps before the repeat is always integral.

Another pattern I've just spotted in your table for prime bases x:

If x ends in 3 or 5, the number of steps appears to be x+1.

If x ends in 1, the number of steps appears to be (x-1)/2.

If x ends in 9... I'm not sure. It looks like it is (x-1)/k, where k is 2 most of the time but is occasionally 4 or 6. I haven't really looked into this closely.

Anyway, I'll try and have a go at proving your conjecture in your last message. I've got a feeling that these prime results will be much harder...

Yours,

Michael

Yeah, I checked the primes against these rules, and I pretty much agree - I think you mean if it ends 3 or 7, then it's (x+1), although this does not happen if its eg 47, where its (x+1)/3.

The pattern seems to be that if x ends in a 3 or a 7, then (x) is a factor of [x+1], and if x ends in a 1 or a 9, then (x) is a factor of [x-1].

3 questions remain, however:
1, There is a number for which this doesn't apply, where (x) is a factor of [x-3] - I don't have it to hand, but I'll get it for later. What's so special about this number?
2, For any given number, which factor of (x) is it?
3,Why is there such a simple rule for such a complicated event?

In ln2=0 in Open Discussions I wrote something at the end which I think amounts to the same thing which you, Michael, noticed about the primes but unfortunately I haven't been able to prove it either. When it is related to which Fibonacci numbers are divisible by a prime I think it may be related to the Lucas Lehmer test for primality but I'm not really sure.

William, the way you work out N (for q) implies that F_2N is divisible by q, i.e. for x=10, N=30 means F_2N =F_2*30 =F₆₀ is divisible by x=10, (I expect you already knew that). There is a rule relating to Fibonacci numbers which says that if F_m is divisible by n then F_am is divisible by n where a,m,n are positive integers. These two facts may help with giving a reason behind your rule for calculating N for a composite number although when I tried I seemed to have too many factors of 2, you may have more luck!

Cheers for the hint, it actually goes a long way to explaining some of it - that's the LCM part of the process explained (although I will probably try to track down the rule you found to see if it yields further insights.

Btw, I checked my records, and I was wrong - every prime under 500 is a factor of either (x+1) or (x-1). Except 2 and 5 of course. Here's the full listing. I divided it into 3 groups - those ending 3 or 7, where the result is x+1, those ending 1 or 9, where the result is (x-1)/2, and the 'anomolies'. The full count of these is:
x+1 - 40
(x-1)/2 - 30
anomolies - 23

x+1:
3
7
13
17
23
37
43
53
67
73
83
97
103
127
137
157
163
167
173
193
197
223
227
257
277
283
293
313
317
337
367
373
383
397
433
443
457
463
467
487

(x-1)/2
11
19
31
41
59
61
71
79
109
131
149
179
191
239
241
251
269
271
311
359
379
389
409
419
431
439
449
479
491
499

For the anomolies, I will have 2 'columns' - I don't know how to use tables, so It'll look bad, I'm afraid - One of n, the other is q in terms of n, eg
107 (n+1)/3
means that when q is 107, n is 36. I chose to express it like this, as I find it more revealing.

2 ?
5 2n
29 (n-1)/4
47 (n+1)/3
89 (n-1)/4
101 (n-1)/4
107 (n+1)/3
113 (n+1)/3
139 (n-1)/6
151 (n-1)/6
181 (n-1)/4
199 (n-1)/18
211 (n-1)/10
229 (n-1)/4
233 (n+1)/9
263 (n+1)/3
281 (n-1)/10
307 (n+1)/7
331 (n-1)/6
347 (n+1)/3
349 (n-1)/4
353 (n+1)/3
401 (n-1)/4
421 (n-1)/10
461 (n-1)/20

The strangest thing I've found is that the hard rule for every prime between 1 and 500 is that if (x mod 10) = 3 or 7, the result is a factor of (n+1), but if (x mod 10) = 1 or 9, the result is a factor of (n-1). What is is about base 10?

William - ah yes, you're right I meant to talk about those ending in 3 and 7, as you guessed. And I missed 47.

Anyway, I?ve just made an attempt at a proof for Andrew's results, i.e. for prime p:

If p = ±1 (mod 10), F(p-1) is a multiple of p
If p = ±3 (mod 10), F(p+1) is a multiple of p

Yesterday I started reading a book entitled 'From Polynomials to Sums of Squares' and in the first chapter it gives a result which may help with the proof.

First of all we extend the idea of modulo to fractions. We define the modulo (to base p) of a/b to be the modulo of a divided by the modulo of b.

So in modulo 7:

¾ = (3/-3) = -1 = 6 (mod 7)

because 4 = -3 (mod 7).

Now the result is (unstated but used implicitly) basically:

Provided you are worked to a prime modulo p, the system behaves sensibly.

So every fraction is equivalent to a SINGLE integer in the range 0 to p-1 (no ambiguity ? so you cannot manipulate ¾ to get any integer other than 6 in the range 0-6, if you?re working mod 7). Also if a is equivalent to c and b is equivalent to d, then ac is equivalent to bd (mod p). Here a, b, c, d are rationals.

This is all very easy to see, but I?ll post my proof of it otherwise.

Now how can this help with Fibonacci? Well first of all I used the Fibonacci recurrence relationship F(n+2) = F(n+1) + F(n) to solve F(n) in terms of n (in analogous fashion to solving 2nd order differential equations) applying initial conditions. (I won't write down my answer here as it looks a bit messy - but I think I've seen it somewhere before.) Now binomially expand the result. In the special case where n is even you get:

2^n-1 F(n) = C(n,1) + 5 C(n,3) + 5² C(n,5) + ... + 5^(n-2)/2 C(n,n-1)

where C(n,r) is n choose r.

So let's start with p = 10k±1. According to Andrew, F(p-1) is a multiple of p. Letting n = p-1:

2^p-2 F(p-1) = C(p-1,1) + 5 C(p-1,3) + 5² C(p-1,5) + ...+ 5^(p-3)/2 C(p-1,p-2)

Consider the right hand side to modulo p.

C(p-1,1) = p-1 = -1
C(p-1,3) = (p-1)(p-2)(p-3)/3! = (-1)(-2)(-3)/3! = -1
C(p-1,5) = (p-1)(p-2)(p-3)(p-4)(p-5)/5! = (-1)(-2)(-3)(-4)(-5)/5! = -1

And so on.

So the right hand side is:

-1-5-5² -...-5^(p-3)/2

= -1(5^(p-1)/2 -1)/4

Now -1/4 cannot be equivalent to 0. So if F(p-1) is to be equivalent to 0, 5^(p-1)/2 -1 must be equivalent to 0. So if p = 10k ±1 we have reduced the problem to proving that:

5^5k = 1 (mod 10k+1)

and

5^5k-1 = 1 (mod 10k-1)

where 10k+1 (in the first case) or 10k-1 in the second case is prime.

Now do exactly the same for p = 10k±3. You end up with 2^p F(p+1) being equivalent to:

1+5^(p-1)/2

(using the fairly obvious fact that C(p,r) is divisible by p for r < p)

so the challenge is to prove that (when substituting p = 10k±3:

5^5k+1 = -1 (mod 10k+3) provided p is prime

and

5^5k-2 = -1 (mod 10k-3)

So once again here are the 4 results we need:

5^5k = 1 (mod 10k+1) where 10k+1 is prime
5^5k-1 = 1 (mod 10k-1) where 10k-1 is prime
5^5k+1 = -1 (mod 10k+3) where 10k+3 is prime
5^5k-2 = -1 (mod 10k-3) where 10k-3 is prime

I'll have a think about these now. In the meantime, get back to me if I haven't explained anything well enough.

Yours,

Michael

By the way, I was just thinking about what Andrew said about the common factors of F(am) and F(m). This seems to be part of a more general rule that:

F(n) = (-1)^r+1 F(n-r) + R(r)F(n-2r)

where R(r) satisfies R(0) = 2, R(1) = 1, R(r) = R(r-1) + R(r-2).

I think I've got this proved by induction but it is extremely messy so I won't write it in here. This shows that:

F(n) = A F(n-r) + B F(n-2r)

where A,B are integers; r is natural.

So if you now let n = 2r you get:

F(2r) = A F(r)

So F(2r) is a multiple of F(r).

Then letting n = 3r, F(3r) = A F(2r) + B F(r). So F(3r) is also a multiple of F(r). And so on: F(ar) is a multiple of F(r).

I haven't really had a chance to think about proving the divisibility results. They seem related to Fermat's Little Theorem (see the discussion under that name in One-One) but it isn't quite specific enough.

Yours,

Michael

OK, I've tidied up the proof somewhat so here goes.

F(n) satisfies:

F(n) = F(n-1) + F(n-2)

but for the time being the initial conditions are indeterminate. We want to prove that:

F(n) = R(r) F(n-r) + (-1)^r+1 F(n-2r)

where R itself satisfies R(n) = R(n-1) + R(n-2) and also R(0) = 2, R(1) = 1. (So it continues 3 4 7 11 etc).

So in other words if you set r = 1 you get:

F(n) = R(1) F(n-1) + (-1)¹⁺¹ F(n-2) = F(n-1) + F(n-2) as we already knew.

First of all we have to convince ourselves that there do exist functions A(r) and B(r) such that

F(n) = A(r) F(n-r) + B(r) F(n-2r)

no matter what n is, or what the initial conditions for F(n) are. To see this set

F(n-2r) = a
F(n-r) = b
F(n) = c

and F(n-2r+1) = k.

Using the recurrence relationships we can see

F(n-2r+2)
F(n-2r+3)
F(n-2r+4)
...
F(n-r-2)
F(n-r-1)

are all linear expressions on a and k.

But F(n-r-2) + F(n-r-1) = F(n-r). So:

(linear expression on a,k) = b

And rearranging:

k = linear expression on a,b.

So:

F(n-2r+1) is linear on a,b. F(n-2r) = a so:

F(n-2r+1)
F(n-2r+2)
...
F(n)

are all linear on a,b

So F(n) is linear on a and b. So there do exist functions A(r) and B(r) such that:

F(n) = A(r) F(n-r) + B(r) F(n-2r)

where A(r) and B(r) are independent of n, and of the initial conditions for F(n).

Now as the inductive hypothesis we shall take for r = k and r = k+1:

A(r) = R(r) and B(r) = (-1)^r+1

where R(r) is as above. Clearly it holds for r = 0 and r = 1. If it holds for r = k and r = k+1:

F(n) = R(k) F(n-k) + (-1)^k+1 F(n-2k)
F(n+1) = R(k+1) F(n-k) + (-1)^k+2 F(n-2k-1)

Add these:

F(n+2) = F(n-k)[R(k) + R(k+1)] + [(-1)^k+1 F(n-2k) + (-1)^k+2 F(n-2k-1)]

F(n+2) = F(n-k)R(k+2) + (-1)^k+3 F(n-2k-2)

Comparing this with:

F(n+2) = F(n-k)A(k+2) + F(n-2k-2)B(k+2)

we can see A(k+2) = R(k+2), B(k+2) = (-1)^k+3 completing the induction.

First of all this shows that if you let F(n) be the Fibonacci numbers (in other words supply the initial conditions F(0) = 0, F(1) = 1) then if you set n = 2r you get:

F(2r) = R(r) F(r) + (-1)^r+1 F(0)

But F(0) = 0 so:

F(2r) = R(r) F(r)
F(3r) = R(r) F(2r) + (-1)^r+1 F(r) = F(r)[R(r)² +(-1)^r ]

etc

So F(ab) is a multiple of F(a) and F(b), where a and b are integers.

Also if you let F(n) = R(n) you get:

R(n) = R(r) R(n-r) + (-1)^r+1 R(n-2r)

Letting n = 2r you get:

R(2r) = R(r)² + 2(-1)^r+1

Another thing we can set F(n) is Gⁿ where G is the Golden ratio. In which case we get the explicit formula for R(n):

Gⁿ = R(r) G^n-r + (-1)^r+1 G^n-2r

G^2r = G^r R(r) + (-1)^r+1

So:

R(r) = [G^2r + (-1)^r ]/G^r

Which isn't as simple as I was hoping.

And I still haven't found a way to show the results we needed to prove Andrew's conjecture (in ln2 = 0). Help anyone....?

Yours,

Michael

As a^p-1 = 1 (mod p),
a^10k = 1 (mod 10k+1) where 10k+1 is prime
a^10k-2 = 1 (mod 10k-1) where 10k-1 is prime
a^10k+2 = 1 (mod 10k+3) where 10k+3 is prime
a^10k-4 = 1 (mod 10k-3) where 10k-3 is prime
so,
5^10k = 1 (mod 10k+1) where 10k+1 is prime
5^10k-2 = 1 (mod 10k-1) where 10k-1 is prime
5^10k+2 = 1 (mod 10k+3) where 10k+3 is prime
5^10k-4 = 1 (mod 10k-3) where 10k-3 is prime

So the exponents are double what we need.

Now, if a^p-1 = 1 (mod p)
then a^p-1 -1 = 0 (mod p),
(a^(p-1)/2 )^2 - 1 = 0 (mod p),
(a^(p-1)/2 - 1)(a^(p-1)/2 + 1) = 0 (mod p),
either, a^(p-1)/2 = 1 (mod p)
or a^(p-1)/2 = -1 (mod p) so proving which one for each type of prime would prove or disprove our results.

"If h is the smallest number such that a^h =1(mod m) then the order of a modulo m is h, or a belongs to the exponent h modulo m." This comes from The Theory of Numbers by Ivan Niven and is probably what we need but I can't seem to find the relevant result that we need. The book shows that h is a divisor of p-1 when m = p but as I've said I can't make the link. If you have a book that discusses the order of a or belonging to the exponent it may help us.

Yes - that's what I got. The modulo of the left hand side in each case is ±1 and it isn't immediately obvious which sign to take. I'm afraid I can't quite grasp the statement made in the book. I'd be grateful if you'd explain what the "order of a modulo m" means or "belongs to the exponent h modulo m". Unfortunately the only book I have on number theory (entitled "From Polynomials to Sums of Squares") is a bit tricky and I'm still on chapter 1! There's also the Penguin Dictionary of Curious and Interesting Numbers which is good. I looked up Fibonacci just now, and it appears that the numbers R(n) I was talking about above are actually called the Lucas numbers, and they confirmed there some of the results connecting Fibonacci and Lucas.

Yours,

Michael

A bit of garbled group theory here guys...

The order n of an element g in the group G is the smallest n such that g^n = e, where e is the identity element. If there is no such number, then g is said to be of infinite order.

So presumably, in modulo arithmetic, the order (modulo m) 'n' of a number 'a' is the smallest number such that a^n = 1 (mod m). And I would be immensely surprised if there weren't some insoluble cases of that too. How about a=4, m=2..
Then there is no such integer n. That of course would work for a being any even number, and m a different even number.

I've tried to write that clearly but I don't think I have succeeded.

I also hope that I understood what Andrew meant, and I haven't explained something fundamentally obvious that you already knew! But as Michael said group theory isn't in A-Levels, and although the result is an adaptation of a modulo theory, that probably isn't in A-Level either.

I recommend "Numbers, Groups and Codes" (a turquoise colour) by someone or other (Cambridge Press I think)... I had this book up until last Friday when I handed it back... DOH!

I think that was just about perfect Neil! I mentioned this because for example we know that;
a³⁰ =1(mod31)
so
5³⁰ =1(mod31) but the smallest n such that
5ⁿ =1(mod31) is n=3 so h=3 (h=order)
so 5^3b =1(mpd31) where b is a positive integer (by raising 5³ to the power b).
This shows that 5¹⁵ =1(mod31) which we want for our proof above.
For our proof we want h to be a divisor of (p-1)/2 whereas if perhaps 3h=p-1 then 5^(p-1)/2 is not equal to 1(modp) because the only exponents which satisfy the equation are multiples of the order.

I hope that makes some sense. I tried to write more about this on Monday night as I realised I hadn't actually explained it but my computer wouldn't let me access NRICH for some reason.

Neil, yes modulo arithmetic isn't in A-Levels either. (Interestingly I first learnt about it in my interview on Dec 6.) I very much like the idea introduced in the book I was reading just now, where you extend modular arithmetic to the rationals, for prime modulos.

In fact I've been wondering whether we can further generalise modulo arithmetic to surds and whether that may help with our problem.

Using this idea I can show that the first two equations we wanted to prove are equivalent to proving the existence of integer a where:

a² = 5 (mod p) for each prime p = ±1 (mod 10).

And the second two are equivalent to proving the existence of b where:

b² = -5 (mod p) for each prime p = ±3 (mod 10)

So it seems I'm OK at re-formulating this problem many, many times, but no good at actually solving it!

Good luck in Maths II everybody,

Michael

I'm not sure how surds would work. From what you said about rationals, we could probably say that the residue b of xⁿ is the residue a of x, to the power of n, ie: b=aⁿ .
Does this help, probably not.

Michael, are you sure about your results, I have a book in which there is an exercise;
4. Determine whether x⁴ =25(mod1013) is solvable, given that 1013 is a prime.
The answers in the back say there is no solutions but x⁴ -25=(x² +5)(x² -5)=0(mod1013) so this would suggest our theory is wrong but I have a program which finds the smallest F(n) such that f(n) is divisible by p. F(507) is divisible by 1013 so also is F(1014) contrary to your result.
I've been trying to read through all the relevant stuff in this book but its taking a while.

Michael - Perhaps you are going in the wrong direction here. By Gauss' theory of quadratic recipricality, the equations

and

x² º q (mod p)

are either:

both solvable or unsolvable

unless

p º q º 3 (mod 4), in this case one is solvable whilst the other is not. Perhaps we should look at mod 4 instead of mod 10.

Kerwin

Yes, you're both right. My argument for the p = ±3 case was utter nonsense. Sorry.

As far as I can make out we are still OK on the p = ±1 case, in other words, I think that the first two equations are still equivalent to proving the existence of a where:

a² = 5 (mod p), p prime, p = 1 (mod 10) (*)

Could well still be wrong. (It is based on applying Fermat's Little Theorem to the integer which is equivalent to sqrt(5).) I think Kerwin's equations would prove (*) to be correct. But anyway, I'll be able to give this my full attention after the STEP exam tomorrow.

Yours,

Michael

Michael - since

is solvable, and 5 º 1 (mod 4), by Gauss theorem of quadratic recipricality,

a² º 5 (mod p) is solvable for all primes p.

Kerwin

Kerwin - what about p = 3? Mod 3, the right hand side is 2. The left hand side is (-1)² , 0² , 1² i.e. 0 or 1. How can this work? I think your proof only holds for p = 1 (mod 5), which does fall under the category p = 1 (mod 10). I'm hoping it will also work for p = -1 (mod 10).

Michael

Obviously the first two cases follow immediately from the Gauss theorem of quadratic recipricality.

x² = ±1 (mod 5)

are solvable by either x = 1 or x = 2. Therefore there does exist an integer a such that:

a² = 5 (mod p) for each prime p, where p = ±1 (mod 10}

Apply Fermat's Little Theorem to a:

a^p-1 = 1 (mod p)

So:

5^(p-1)/2 = 1 (mod p)

(because x² = 5 (mod p))

which gives the first two cases.

Michael

Wow. I checked in after doing a couple of exams, and this entire thread has gotten so complicated - I apologise in advance for any stupid mistakes I make from now on - it'd be simply because I don't understand.

Starting with Michael's message Saturday morning: I think we have different notation, as you state
If p = ±1 (mod 10), F(p-1) is a multiple of p
If p = ±3 (mod 10), F(p+1) is a multiple of p
but eg if p = 11, F(10) is 30. Shouldn't it be
If p = ±1 (mod 10), F(p) is a factor of p-1
If p = ±3 (mod 10), F(p) is a factor of p+1?

Then you talk about fractions in modulus arithmatic, which I semi-agree with, but need to know: What is (7/5) mod 10? I can't work out how to get it.

Also, you talk about a messy step for which you binomially expand the special case of F(n). I would like to hear more about this, especially where the factors of 5 come in.

Next, I can't really see where it is that allows p=±1(mod10) but not p=±1(mod 6) etc... or what rule states which factor each is going to be, particularly why the vast majority are in one set but some others are in another related set

A whole load of my other queries are based on those 3, so I'd better wait and see if I understand rather than getting you to explain everything.

Also, you're talking about
x² =p (mod q)
and
x² =q (mod p)
being soluble
why can't we say that that's analogous to
p(modq) = q(modp)
, then given that either p> q, q> p or p=q,

if p=q then x² = q(modq), so x² mod q = 0
therefore q is a factor of x²

if p> q then q(mod p)=q
so p(modq)=q
thus p-nq=q
p=q(1+n)
q is a factor of p
p(modq)=0
thus x² = 0

I probably messed up somewhere, but I can't see how if x² = "this" and x² = "that", how it can't be that "this"="that", even in clock arithmetic.

Also what was STEP and how did it go?

Bill Johnson

As for your this and that, I haven't been following this, but I would expect it is a congruence notation confusion (we can't write the three-bar equivalence sign, so we just use =.

Neil M

Hi William, -

You're right, I think we do have different notation. I'm using F(n) as the nth Fibonacci number. F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2). Apologies for not explaining properly.

For the time being I'll talk about Andrew's hypotheses in "ln 2 = 0" . Maybe a bit later we can come onto how that helps with Fibonacci in Clock Arithmetic. It is related to the results your program gave for prime bases. But let's leave that for the moment. Andrew said:

If p = ±1 (mod 10) then F(p-1) is a multiple of p.
If p = ±3 (mod 10) then F(p+1) is a multiple of p

First of all we work out an explicit formula for F(n) - the nth Fibonacci number. We know:

F(n) = F(n-1) + F(n-2)

Suppose there is a solution to this equation of the form F(n) = Qⁿ for some number Q to be determined. Write this into the equation:

Qⁿ = Q^n-1 + Q^n-2

Q² = Q + 1
(Q-1/2)² = 5/4
Q = (1 ±sqrt(5))/2

So we know that

[(1+sqrt(5))/2]ⁿ

and

[(1-sqrt(5))/2]ⁿ

both satisfy the equation F(n) = F(n-1) + F(n-2).

Next you can convince yourself that sticking a constant factor outside these two expressions won't make a difference. So for constants A,B the following expressions satisfy F(n) = F(n-1) + F(n-2):

A[(1+sqrt(5))/2]ⁿ

and

B[(1-sqrt(5))/2]ⁿ

Also the sum of these two will satisfy the formula. So we have a general solution to F(n) as

F(n) = A[(1+sqrt(5))/2]ⁿ +B[(1-sqrt(5))/2]ⁿ

(We are guarenteed that this will satisfy F(n) = F(n-1) + F(n-2).)

Now F(0) = 0, F(1) = 1. So:

0 = A + B
1 = A(1+sqrt(5))/2 + B(1-sqrt(5))/2

So A = 1/sqrt(5), B = -1/sqrt(5)

And the formula for the nth Fibonacci number is:

F(n) = 1/sqrt(5) [(1+sqrt(5))/2]ⁿ - 1/sqrt(5) [(1-sqrt(5))/2]ⁿ

Already you can see why 5s are looking significant! Now the next step is the binomial expansion of the right hand side. I'll leave that to you for the moment. Please get back to me with any mistakes so far... I'm sorry if it looks like we've deviated from the original problem a lot, but I think general principles about Fibonacci will help here.

(BTW - do you know about 2nd order differential equations? If you do then that's great because the method above of solving discrete equations is almost completely analogous to solving continuous differential equations so should be easy to understand.)

Just one last thing - you point out that 7/5 (mod 10) cannot be equivalent to an integer. We are only guarenteed to be able to find an integer if the base is prime. (Actually I'd be grateful if someone could confirm this. If I'm wrong then this will have messed up about the last 10 posts.) I think this can be proven by using Euclid's algorithm which is described elsewhere on NRICH (I think under Fibonacci Coprime, One to One?). Neil knows much more about that than I do, because it is not covered by A-Levels but is covered by SYS (the Scottish equivalent).

So the problem with 7/5 (mod 10) is that the number on the denominator (5) shares a prime factor with 10. We need both the denominator to be coprime with the base, as Euclid's algorithm shows. But in the examples we did above the base was prime. And the denominator of the fractions we were considering weren't a factor of the prime base. So we're okay.

By the way, we can get the three bar thing, but I don't see any problem with =.

Oh and there was a mistake in my last message. I said in brackets "because x² = 5 (mod p)" when it should have been a² = 5 (mod p).

Yours,

Michael

I noticed this soon after my original posting in ln2=0 but I only thought about it again today. p = ±1 (mod 10) is in effect the same as p = ±1 (mod 5) and p = ±3 (mod 10) is in effect the same as p = ±2 (mod 5). I don't know if this helps at all and you may have already realised it but it removes the factor of 2 and produces yet another occurance of the mysterious 5 by itself!
Michael, when you have time could you post the proof of the reduction to the quadratic case, I'm intrigued.

I think the following works for the proof, but I'm never confident about this sort of thing.

p is prime st p = ±1 (mod 10)

Let x be such that x² = 5 (mod p).

(Assume such an x exists. Kerwin has proved this above for p = ±1 (mod 10), using a theorem of Gauss.)

Apply Fermat's Little Theorem to x,p.

x^p-1 = 1 (mod p)

So:

[x² ]^(p-1)/2 = 1 (mod p)

But x² = 5 (mod p). By the law that:

a^x = b^x (mod c) if a = b (mod c) we can deduce that:

5^(p-1)/2 = 1 (mod p)

If p = 10k+1:

5^5k = 1 (mod p)

While if p = 10k - 1:

5^5k-1 = 1 (mod p)

I think that works but please check!

Yours,

Michael

Michael -

I was answering the question

if p º 3 (mod 4) then we have -5 º p º 3 (mod 4)

since x² º p (mod -5) is not solvable, the result follows.

However, if p º 1 (mod 4) then the equation b² º -5 (mod p) is not solvable.
Kerwin

Well I think I follow that. The reason b² = p (mod -5) is not soluble is that no square can be 3,7 mod 10 (it appears, from quick hand calculations). Anyway the real challenge is to prove the Gauss theorem we're using. Also we still have to prove the 3rd and 4th equations (you agree we've shown the first two, given Gauss' contribution?).

Thanks

Michael

Kerwin - I'm confused about the Gauss theorem. Suppose we let p = q (give them the actual same value, not mod anything).

Also suppose p = q = 3 (mod 4).

Now the Gauss theorem says that of the two equations:

x² = p (mod p)
x² = p (mod p)

one is soluble and the other isn't! Help!!

Michael

Michael, a condition of the Gauss reciprocity law is that p and q are distinct odd primes. Your proof above of the reduction looks correct to me, very clever, I think its one of the nice things about questions like this that small steps can make things so much easier.

Andrew - that's very generous of you.

Thanks a lot for sorting out my confusion surrounding the Gauss theorem. It was beginning to drive me insane!

Yours,

Michael

Michael-

As regards squares mod 10, you only have to show that none of the squares of integers between 1 and 9 are congruent to 3 or 7, because we are using a decimal system, and the last digit of, say 493² will come from 3² . So, of the non-evens, 1² = 1, 3² = 9, 5² = 5, 7² =9 and 9² = 1, and so on in a pattern for the odd numbers (1,9,5,9,1). The even pattern is (0,4,6,6,4). So squares can only be congruent to 0,1,4,5,6,9 mod 10.

Neil M

Yes exactly - that's how I did it!

Michael

So where does that leave us with respect to solving the overall system?

Basically we have got a few results regarding prime bases (though even this isn't simple) but I don't think anyone's explained your pattern for the product of two primes. I'll see if I can write coherently what we do and don't know in the morning. Were there any problems in my June 29 message? It is quite important to get the explicit formula for Fibonacci as this tells us about divisibility results. It may also be useful to understand why the relationship

F(n) = R(r)F(n-r) + (-1)^r+1 F(n-2r)

holds (with R = Lucas numbers and F = any Fibonacci type sequence)

Sorry again,

Michael

Hi William,

I'm still trying to see exactly what we have and haven't worked out about prime numbers. But for the moment I'

Just one thing about your 'solving the fibonacci equations' - you assume a common ratio, when there is never actually one, merely an inclination to approach 1.618 - can you solve these still?

William - sorry I missed your last message. It is a good point you raise. But the point is that we're not assuming that the Fibonacci numbers can be written in the form t ⁿ - rather we're assuming that there is a solution of this form to the equation:

F(n) = F(n-1) + F(n-2)

[NB we haven't asserted any initial conditions like F(0) = 0, F(1) = 1]

So to find any solution of the form t ⁿ we get:

t ² = t + 1

and

t = (1+sqrt(5))/2
t = (1-sqrt(5))/2

So

F(n) = [(1+sqrt(5))/2]ⁿ and
F(n) = [(1-sqrt(5))/2]ⁿ

are both solutions to the equation

F(n) = F(n-1) + F(n-2)

[Although they don't yet satisfy F(0) = 0, F(1) = 1.]

Now can you see that:

F(n) = A[(1+sqrt(5))/2]ⁿ and
F(n) = B[(1-sqrt(5))/2]ⁿ

also satisfy the difference equation? (A,B constant).

If you can see that you should be able to see that:

F(n) = A[(1+sqrt(5))/2]ⁿ + B[(1-sqrt(5))/2]ⁿ

is also a solution of:

F(n) = F(n-1) + F(n-2)

Finally you set the initial conditions. F(0) = 0, F(1) = 1. What do you make A,B?

Have you learnt about second order differential equations? It would make it easier to explain as the two methods are analogous.

BTW - I still haven't thought of a way to prove your prime² conjecture. It is going to need a new insight. At the moment I'm just getting bogged down in algebra. Perhaps someone (anyone) could help here...

Yours,

Michael

Are there any composite numbers which satisfy our two equations from above;

if n = ±1 (mod 10) then F(n-1) is a multiple of n.
if n = ±3 (mod 10) then F(n+1) is a multiple of n?

That probably should have read: either of our two equations from above

Here is a proof for the cases where p = 10x ± 3.

First a few definitions. If a and m are relatively prime, (a,m) = 1, then a is called a quadratic residue modulo m if the congruence x² = a(mod m) has at least one solution in x. If there is no solution then a is called a quadratic nonresidue modulo m. For example 1 is a quadratic residue modulo 3 but 2 is a quadratic non-residue modulo 3. If p denotes an odd prime and (a,p) = 1 then the Legendre symbol (a/p) is defined to be 1 if a is a quadratic residue, -1 if a is a quadratic nonresidue modulo p. For example (1/3) = 1, (2/3) = (-1/3) = -1.

Let p be an odd prime and (a,p) = 1, we know that;

a^p-1 ? 1 = 0 (mod p) so,
[a^(p-1)/2 - 1] * [a^(p-1)/2 +1] = 0 (mod p)
so either;
a^(p-1)/2 = 1 (mod p) or
a^(p-1)/2 = -1 (mod p) are true but obviously not both.

Let (a/p) = 1 then x² = a (mod p) has a solution, say x₀ , so a = x₀ ² (mod p).
Raising this to the power of (p-1)/2 gives;
a^(p-1)/2 = x₀ ^p-1 = 1 = (a/p) (mod p).

Now let (a/p) = -1 which means x² = a (mod p) has no solution so;
a^(p-1)/2 ¹ 1 (mod p) which implies
a^(p-1)/2 = -1 = (a/p) (mod p).

In general therefore;
a^(p-1)/2 = (a/p) (mod p) (*)

For our problem we have a = 5 and either p = 10x ± 1 in which case we want to show that (5/p) = 1 or p = 10x ± 3
In which case we want to show that (5/p) = -1.

If (a,p) = (b,p) = 1 then the following can be deduced from (*);
(1) (ab/p) = (a/p) * (b/p)
(2) (1/p) = 1
(3) (-1/p) = (-1)^(p-1)/2
(4) ((a + np)/p) = (a/p) where n is an integer.

The Gaussian reciprocity law can also be expressed using the Legendre symbol, if p and q are distinct odd primes;
(p/q) * (q/p) = (-1)^{[(p-1)/2][(q-1)/2]}

So (5/p) * (p/5) = (-1)^{[(5-1)/2][(p-1)/2]}
= (-1)^{2 * [(p-1)/2]}
= (-1)^(p-1)
= 1.

As (a/p) = ± 1 they can be shifted from one side of an equation to the other so (5/p) * (p/5) = 1 implies (5/p) = (p/5).

Now taking p = 10x + 1 and using (4) and (2),
(5/(10x + 1)) = ((10x + 1)/5) = (1/5) = 1.

Taking p = 10x - 1 and using (4) and (3),
(5/(10x - 1)) = ((10x - 1)/5) = (-1/5) = (-1)^(5-1)/2 = 1.

Taking p = 10x + 3 and using (4), (3) and the Gaussian reciprocity law,
(5/(10x + 3)) = ((10x + 3)/5) = (3/5) = (5/3) = (2/3) =(-1/3) = (-1)^(3-1)/2 = -1.

Taking p = 10x - 3 and using (4), (3) and (1),
(5/(10x - 3)) = ((10x - 3)/5) = (-3/5) = (-1/5) * (3/5) = 1 * -1 = -1.

This proves all four of the formulas that we want to show. Some of the above we already knew but I decided to write it again for completeness.