By William Johnson (P2617) on Tuesday, June 13, 2000 - 03:19 am:
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?
By Johannes Kuhr (Jfk23) on Friday, June 16, 2000 - 06:36 pm:
This sounds very interesting, but what are your results? And what are the rules you found?
By William Johnson (P2617) on Sunday, June 18, 2000 - 04:42 am:
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.
By Kerwin Hui (P1312) on Sunday, June 18, 2000 - 08:41 am:
William - are you sure about your program? It seems to me that
you test on the pair (F2N-1,F2N) and then
(F2N+1,F2N+2), with the omission of
(F2N,F2N+1) for all positive integer N that
you labelled.
Kerwin
By William Johnson (P2617) on Tuesday, June 20, 2000 - 01:24 am:
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.
By Michael Doré (P904) on Tuesday, June 20, 2000 - 11:44 am:
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
By Michael Doré (P904) on Tuesday, June 20, 2000 - 08:05 pm:
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
By William Johnson (P2617) on Wednesday, June 21, 2000 - 03:05 am:
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.
By Michael Doré (P904) on Thursday, June 22, 2000 - 08:46 pm:
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
By William Johnson (P2617) on Friday, June 23, 2000 - 12:43 am:
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?
By Andrew Smith (P2517) on Friday, June 23, 2000 - 10:18 pm:
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 F2N
is divisible by q, i.e. for x=10, N=30 means
F2N=F2*30=F60 is divisible by
x=10, (I expect you already knew that). There is a rule relating to
Fibonacci numbers which says that if Fm is divisible by
n then Fam 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!
By William Johnson (P2617) on Saturday, June 24, 2000 - 12:38 am:
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?
By Michael Doré (P904) on Saturday, June 24, 2000 - 06:58 am:
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:
2n-1F(n) = C(n,1) + 5 C(n,3) + 52 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:
2p-2 F(p-1) = C(p-1,1) + 5 C(p-1,3) + 52
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-52-…-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:
55k = 1 (mod 10k+1)
and
55k-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
2pF(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:
55k+1 = -1 (mod 10k+3) provided p is prime
and
55k-2 = -1 (mod 10k-3)
So once again here are the 4 results we need:
55k = 1 (mod 10k+1) where 10k+1 is prime
55k-1 = 1 (mod 10k-1) where 10k-1 is prime
55k+1 = -1 (mod 10k+3) where 10k+3 is prime
55k-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 Michael Doré (P904) on Saturday, June 24, 2000 - 08:35 pm:
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+1F(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
By Michael Doré (P904) on Monday, June 26, 2000 - 12:14 pm:
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)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+3F(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+1F(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)2+(-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+1R(n-2r)
Letting n = 2r you get:
R(2r) = R(r)2 + 2(-1)r+1
Another thing we can set F(n) is Gn where G is the
Golden ratio. In which case we get the explicit formula for
R(n):
Gn = R(r) Gn-r +
(-1)r+1Gn-2r
G2r = Gr R(r) + (-1)r+1
So:
R(r) = [G2r + (-1)r]/Gr
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
By Andrew Smith (P2517) on Monday, June 26, 2000 - 10:33 pm:
As ap-1 = 1 (mod p),
a10k = 1 (mod 10k+1) where 10k+1 is prime
a10k-2 = 1 (mod 10k-1) where 10k-1 is prime
a10k+2 = 1 (mod 10k+3) where 10k+3 is prime
a10k-4 = 1 (mod 10k-3) where 10k-3 is prime
so,
510k = 1 (mod 10k+1) where 10k+1 is prime
510k-2 = 1 (mod 10k-1) where 10k-1 is prime
510k+2 = 1 (mod 10k+3) where 10k+3 is prime
510k-4 = 1 (mod 10k-3) where 10k-3 is prime
So the exponents are double what we need.
Now, if ap-1 = 1 (mod p)
then ap-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 ah=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.
By Michael Doré (P904) on Monday, June 26, 2000 - 10:52 pm:
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
By Neil Morrison (P1462) on Tuesday, June 27, 2000 - 01:50 pm:
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!
By Andrew Smith (P2517) on Tuesday, June 27, 2000 - 10:30 pm:
I think that was just about perfect Neil! I mentioned this
because for example we know that;
a30=1(mod31)
so
530=1(mod31) but the smallest n such that
5n=1(mod31) is n=3 so h=3 (h=order)
so 53b=1(mpd31) where b is a positive integer (by
raising 53 to the power b).
This shows that 515=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)/2is 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.
By Michael Doré (P904) on Wednesday, June 28, 2000 - 04:01 pm:
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:
a2 = 5 (mod p) for each prime p = ±1 (mod
10).
And the second two are equivalent to proving the existence of b
where:
b2 = -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
By Neil Morrison (P1462) on Wednesday, June 28, 2000 - 06:47 pm:
I'm not sure how surds would work. From what you said about
rationals, we could probably say that the residue b of
xn is the residue a of x, to the power of n, ie:
b=an.
Does this help, probably not.
By Andrew Smith (P2517) on Wednesday, June 28, 2000 - 10:43 pm:
Michael, are you sure about your results, I have a book in which
there is an exercise;
4. Determine whether x4=25(mod1013) is solvable, given
that 1013 is a prime.
The answers in the back say there is no solutions but
x4-25=(x2+5)(x2-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.
By Kerwin Hui (P1312) on Wednesday, June 28, 2000 - 10:52 pm:
Michael - Perhaps you are going in the wrong direction here. By
Gauss' theory of quadratic recipricality, the equations
x2ºp (mod q)
and
x2º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
By Michael Doré (P904) on Thursday, June 29, 2000 - 12:41 am:
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:
a2 = 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
By Kerwin Hui (P1312) on Thursday, June 29, 2000 - 08:35 am:
Michael - since
x2ºpº1 (mod 5)
is solvable, and 5º1 (mod 4}, by
Gauss theorem of quadratic recipricality,
a2º5 (mod p) is solvable
for all primes p.
Kerwin
By Michael Doré (P904) on Thursday, June 29, 2000 - 09:52 am:
Kerwin - what about p = 3? Mod 3, the right hand side is 2. The
left hand side is (-1)2, 02, 12
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
By Michael Doré (P904) on Thursday, June 29, 2000 - 11:12 am:
Obviously the first two cases follow immediately from the Gauss
theorem of quadratic recipricality.
x2 = ±1 (mod 5)
are solvable by either x = 1 or x = 2. Therefore there does exist
an integer a such that:
a2 = 5 (mod p) for each prime p, where p = ±1
(mod 10}
Apply Fermat's Little Theorem to a:
ap-1 = 1 (mod p)
So:
5(p-1)/2 = 1 (mod p)
(because x2 = 5 (mod p))
which gives the first two cases.
Michael
By William Johnson (P2617) on Thursday, June 29, 2000 - 05:58 pm:
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
x2=p (mod q)
and
x2=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 x2 = q(modq), so x2 mod q =
0
therefore q is a factor of x2
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 x2 = 0
I probably messed up somewhere, but I can't see how if
x2= "this" and x2= "that", how it can't be
that "this"="that", even in clock arithmetic.
Also what was STEP and how did it go?
Bill Johnson
By Neil Morrison (P1462) on Thursday, June 29, 2000 - 06:26 pm:
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
By Michael Doré (P904) on Thursday, June 29, 2000 - 09:02 pm:
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) = Qn for some number Q to be determined. Write this
into the equation:
Qn = Qn-1 + Qn-2
Q2 = Q + 1
(Q-1/2)2 = 5/4
Q = (1 ±sqrt(5))/2
So we know that
[(1+sqrt(5))/2]n
and
[(1-sqrt(5))/2]n
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]n
and
B[(1-sqrt(5))/2]n
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]n+B[(1-sqrt(5))/2]n
(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]n - 1/sqrt(5)
[(1-sqrt(5))/2]n
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 x2 = 5 (mod p)" when it should have been
a2 = 5 (mod p).
Yours,
Michael
By Andrew Smith (P2517) on Thursday, June 29, 2000 - 10:34 pm:
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.
By Michael Doré (P904) on Thursday, June 29, 2000 - 10:56 pm:
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 x2 = 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.
xp-1 = 1 (mod p)
So:
[x2](p-1)/2 = 1 (mod p)
But x2 = 5 (mod p). By the law that:
ax = bx (mod c) if a = b (mod c) we can
deduce that:
5(p-1)/2 = 1 (mod p)
If p = 10k+1:
55k = 1 (mod p)
While if p = 10k - 1:
55k-1 = 1 (mod p)
I think that works but please check!
Yours,
Michael
By Kerwin Hui (P1312) on Friday, June 30, 2000 - 11:09 pm:
Michael -
I was answering the question
a2º5 (mod p),
pº±1 (mod 10)
in the above discussion(some time ago)
Anyway, for
b2ch{==}-5 (mod p), p±3 (mod 10)
if pº3 (mod 4) then we have
-5ºpº3 (mod 4)
since x2ch{==}p (mod -5) is not solvable, the result
follows.
However, if pº1 (mod 4) then the
equation b2º-5 (mod p)
is not solvable.
Kerwin
By Michael Doré (P904) on Friday, June 30, 2000 - 11:56 pm:
Well I think I follow that. The reason b2 = 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
By Michael Doré (P904) on Saturday, July 1, 2000 - 10:59 am:
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:
x2 = p (mod p)
x2 = p (mod p)
one is soluble and the other isn't! Help!!
Michael
By Andrew Smith (P2517) on Saturday, July 1, 2000 - 02:04 pm:
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.
By Michael Doré (P904) on Saturday, July 1, 2000 - 02:36 pm:
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
By Neil Morrison (P1462) on Saturday, July 1, 2000 - 06:30 pm:
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
4932 will come from 32. So, of the non-evens,
12 = 1, 32 = 9, 52 = 5,
72=9 and 92 = 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
By Michael Doré (P904) on Sunday, July 2, 2000 - 11:30 am:
Yes exactly - that's how I did it!
Michael
By William Johnson (P2617) on Wednesday, July 5, 2000 - 02:35 am:
So where does that leave us with respect to solving the overall system?
By Michael Doré (P904) on Wednesday, July 5, 2000 - 11:35 pm:
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+1F(n-2r)
holds (with R = Lucas numbers and F = any Fibonacci type
sequence)
Sorry again,
Michael
By Michael Doré (P904) on Thursday, July 6, 2000 - 10:51 pm:
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’ll deal with how to combine prime numbers. This deals with
the patterns you pointed out in your second message.
Let F(n) = nth Fibonacci number (F(0) = 0, F(1) = 1).
Suppose a steps are required for base x, and b steps are required
for base y. Let x,y be coprime (i.e. x,y have no common factor
>1). We want to show that the number of steps required in base
xy is the lowest common multiple of a,b.
f(a) = 0 (mod x), f(a+1) = 1 (mod x)
Therefore f(p) = 0 (mod x) if and only if p = 0 (mod a).
Also f(p) = 0 (mod y) if and only if p = 0 (mod b).
So if f(p) = 0 (mod xy) we require p = 0 (mod a), p = 0 (mod b)
because a,b are co-prime. Therefore we require p = 0 (mod ab). We
now must show this is sufficient as well as necessary.
We know f(p) = f(q) (mod x) if p = q (mod a), and f(p) = f(q) (mod
y) if p = q (mod b) for all integral p, q. So if r is a multiple of
p,q then f(r) = 0 (mod p), f(r) = 0 (mod q); so f(r) = 0 (mod pq)
as p,q are coprime. In the same way f(r) = 1 (mod p), f(r) = 1 (mod
q); so f(r) = 1 (mod pq). Therefore the number of steps required
under base xy is (no. in base x)*(no. in base y) provided that x,y
are coprime.
Now if what about the number of steps under base x2
where x is prime. You claimed at the start of the discussion that
this was equal to the of the number of steps required for base x
multiplied by x. I am now sure how to prove this but it certainly
looks true. I'll keep trying.
Yours,
Michael
By William Johnson (P2617) on Sunday, July 9, 2000 - 04:18 am:
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?
By Michael Doré (P904) on Wednesday, July 12, 2000 - 07:03 pm:
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 tn - 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 tn we get:
t2 = t + 1
and
t = (1+sqrt(5))/2
t = (1-sqrt(5))/2
So
F(n) = [(1+sqrt(5))/2]n and
F(n) = [(1-sqrt(5))/2]n
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]n and
F(n) = B[(1-sqrt(5))/2]n
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]n +
B[(1-sqrt(5))/2]n
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
prime2 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
By Andrew Smith (P2517) on Thursday, July 13, 2000 - 10:31 pm:
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?
By Andrew Smith (P2517) on Thursday, July 13, 2000 - 10:33 pm:
That probably should have read: either of our two equations from above
By Andrew Smith (P2517) on Tuesday, July 25, 2000 - 08:07 pm:
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
x2 = 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;
ap-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 x2 = a (mod p) has a solution, say
x0, so a = x02 (mod p).
Raising this to the power of (p-1)/2 gives;
a(p-1)/2 = x0p-1 = 1 = (a/p) (mod
p).
Now let (a/p) = -1 which means x2 = 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.
Copyright © 2003.
University of Cambridge. All rights reserved. NRICH is part of
the family of activities in the Millennium Mathematics Project, which
also includes the Plus and
Motivate sites.
email: nrich@damtp.cam.ac.uk