# Elementary number theory¶

## Taking modular powers¶

How do I compute modular powers in Sage?

To compute \(51^{2006} \pmod{97}\) in Sage, type

```
sage: R = Integers(97)
sage: a = R(51)
sage: a^2006
12
```

Instead of `R = Integers(97)`

you can also type
`R = IntegerModRing(97)`

. Another option is to use the interface
with GMP:

```
sage: 51.powermod(99203843984,97)
96
```

## Discrete logs¶

To find a number \(x\) such that
\(b^x\equiv a \pmod m\) (the discrete log of
\(a \pmod m\)), you can call ‘s `log`

command:

```
sage: r = Integers(125)
sage: b = r.multiplicative_generator()^3
sage: a = b^17
sage: a.log(b)
17
```

This also works over finite fields:

```
sage: FF = FiniteField(16,"a")
sage: a = FF.gen()
sage: c = a^7
sage: c.log(a)
7
```

## Prime numbers¶

How do you construct prime numbers in Sage?

The class `Primes`

allows for primality testing:

```
sage: 2^(2^12)+1 in Primes()
False
sage: 11 in Primes()
True
```

The usage of `next_prime`

is self-explanatory:

```
sage: next_prime(2005)
2011
```

The Pari command `primepi`

is used via the command
`pari(x).primepi()`

. This returns the number of primes
\(\leq x\), for example:

```
sage: pari(10).primepi()
4
```

Using `primes_first_n`

or `primes`

one can check that, indeed,
there are \(4\) primes up to \(10\):

```
sage: primes_first_n(5)
[2, 3, 5, 7, 11]
sage: list(primes(1, 10))
[2, 3, 5, 7]
```

## Divisors¶

How do you compute the sum of the divisors of an integer in Sage?

Sage uses `divisors(n)`

for the list of divisors of \(n\),
`number_of_divisors(n)`

for the number of divisors of \(n\)
and `sigma(n,k)`

for the sum of the \(k\)-th powers of the divisors
of \(n\) (so `number_of_divisors(n)`

and `sigma(n,0)`

are the same).

For example:

```
sage: divisors(28); sum(divisors(28)); 2*28
[1, 2, 4, 7, 14, 28]
56
56
sage: sigma(28,0); sigma(28,1); sigma(28,2)
6
56
1050
```

## Quadratic residues¶

Try this:

```
sage: Q = quadratic_residues(23); Q
[0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
sage: N = [x for x in range(22) if kronecker(x,23)==-1]; N
[5, 7, 10, 11, 14, 15, 17, 19, 20, 21]
```

Q is the set of quadratic residues mod 23 and N is the set of non-residues.

Here is another way to construct these using the `kronecker`

command (which is also called the “Legendre symbol”):

```
sage: [x for x in range(22) if kronecker(x,23)==1]
[1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
sage: [x for x in range(22) if kronecker(x,23)==-1]
[5, 7, 10, 11, 14, 15, 17, 19, 20, 21]
```