Talk:Quadratic reciprocity

From Wikipedia, the free encyclopedia

Dear DYLAN LENNON,

Could you please explain how you intend to use quadratic reciprocity to prove fermat's theorem on sums of two squares. The only part that I can see is vaguely relevant is the first supplementary theorem, i.e. that , which is by far the most trivial part of QR. (I have taken the liberty of reverting your edit again until you can provide an explanation.) Dmharvey 01:53, 5 February 2006 (UTC)

You can learn by reading this note. (http://www.math.nmsu.edu/~history/book/numbertheory.pdf) Good luck DYLAN LENNON 02:45, 5 February 2006 (UTC)

I've had a look, and I can't find what you mean. Could you give a page number perhaps? Even better, which paragraph/sentence supports your claim? Dmharvey 02:50, 5 February 2006 (UTC)

[edit] ZX81

There is this lovely line in the ZX81 manual:

65537 is a Fermat prime, 2¹⁶ + 1. Use this, and Gauss's Law of Quadratic Reciprocity, to prove that 75 is a primitive root modulo 65537.

Needless to say I am none the wiser!

Having now discovered the primitive root modulo n page, it transpires that all I needed to do was to verify that

[edit] Python code for residue table

I started trying to make a table of residues to illustrate quadratic reciprocity, but it soon got very painful to do by hand. So I wrote a Python script (my first!) to do it for me. Of course, just editing the script here won't update the table, you'll have to run it on your own machine :-)

    # find primes from 3 up to max
    max = 50
    primes = []
    for n in range(3, max):
        composite = False
        for d in range(2, n-1):
            if n % d == 0:
                composite = True
                break
        if not composite:
            primes.append(n)
            
    count = len(primes)

    yes_marker = '✓'   # tick (U.S. "check") for residues
    no_marker  = '✗'   # cross for non-residues

    def colortag(n):
        if n % 4 == 1:
            return 'bgcolor=#e0ffff'
        else:
            return 'bgcolor=#ffe0e0'

    # computes Legendre symbol (a/q)
    # assumes a and q positive, q prime, (a, q) = 1
    def legendre(a, q):
        for n in range(1, q-1):
            if (n * n) % q == a % q:
                return 1;
        return -1;
        
    # print table header
    print '{| class="wikitable"'
    print '|-'
    print '| || colspan=' + str(count+1), 'align="center" |', "''p''"
    print '|-'
    print '| rowspan=' + str(count+1), "|  ''q''  || ",
    for p in primes:
        print '||', colortag(p), 'align="center" style="border-bottom:2px solid" |', "'''" + str(p) + "'''", 
    print

    # now the main table
    for q in primes:
        # first column
        print '|-'
        print '|', colortag(q), 'align="right" style="border-right:2px solid" |', "''' " + str(q) + " '''",

        # remaining columns
        for p in primes:
            print '||', colortag(1+(p-1)*(q-1)/2), '|',

            if p == q:
                print ' ',
            else:
                # symbol for (p/q)
                if legendre(p, q) == 1:
                    print yes_marker,
                else:
                    print no_marker,

                if legendre(q, p) == 1:
                    print yes_marker,
                else:
                    print no_marker,
        print
            
    print '|}'

Dmharvey 03:22, 21 April 2006 (UTC)