Monday, September 15th, 2025¶

Last time we added code comments to our is_prime to explain how the code works. We also discussed using Markdown cells above code cells to explain what the code will do and how it will work.

Exercise: Using Markdown and LaTeX, explain what the is_prime function does and how it works.

In [12]:
from math import sqrt

def is_prime(n):                             # Define a function is_prime
    n_is_prime = True                        # Define a Boolean that is True when n is 
                                             # prime, false otherwise. We will assume that
                                             # n is prime unless we can show otherwise

    for d in range(2,int(sqrt(n))+1):        # Loop through possible divisors d
        if n % d == 0:                       # Check if n is divisble by d
            n_is_prime = False               # If so, then n is not prime...
            break                            # ... and we can stop looking for divisors
            
    if n_is_prime:                           # If no divisor was found, then n must be prime
        return True
    else:                                    # Otherwise, a divisor was found and n is not prime
        return False
In [14]:
from math import sqrt

def is_prime(n):                             # Define a function is_prime
    for d in range(2,int(sqrt(n))+1):        # Loop through possible divisors d
        if n % d == 0:                       # Check if n is divisble by d
            return False
    return True

Project 1¶

Modular arithmetic and congruences¶

See Project 1 page for an introduction to modular arithmetic and congruences.

From the project page, we say that a number $n$ is "prime-like" if

$$a^n \equiv a\pmod{n}$$ for all integers $0 \leq a < n$.

Exercise: Write a function is_prime_like that takes in an integer n and returns True if n is prime-like and False if not.

In [15]:
def is_prime_like(n):
    for a in range(n):
        if a**n % n != a % n:
            return False
    return True

Note: See project page for details about the operation a**n % n. This turns out to be much too slow for our needs.

In [20]:
help(pow)

Help on built-in function pow in module builtins:

pow(base, exp, mod=None)
    Equivalent to base**exp with 2 arguments or base**exp % mod with 3 arguments

    Some types, such as ints, are able to use a more efficient algorithm when
    invoked using the three argument form.
In [16]:
is_prime_like(3)
Out[16]:
True
In [17]:
is_prime_like(4)
Out[17]:
False
In [18]:
is_prime_like(561)
Out[18]:
True
In [19]:
is_prime(561)
Out[19]:
False

Exercise: Write a function is_false_prime(n) that returns True if n is a false prime and False otherwise.

In [23]:
def is_false_prime(n):
    if is_prime_like(n) and not is_prime(n):
        return True
    else:
        return False

Note: The is_false_prime function above has a critical problem that will us from finding 20 false primes in a reasonable amount of time.

In [24]:
is_false_prime(561)
Out[24]:
True
In [25]:
is_false_prime(29)
Out[25]:
False
In [26]:
is_false_prime(4)
Out[26]:
False

Exercise: Write a function that takes in an integer n and returns a list of prime numbers that divide n.

In [ ]:

Exercise: Modify the function from the previous exercise to return the primary decomposition of n. That is, modify the code to account for the multiplicity of each prime divisor.

In [ ]:

More about functions¶

Positional arguments and keyword arguments¶

So far, we've discussed defining functions that take in some number of input variables. For example, we defined the is_power function that took in two inputs, namely n and power.

In [27]:
def is_power(n,power):
    root_n = n**(1/power)
    if round(root_n)**power == n:
        return True
    else:
        return False

When we call a function, we can simply enter values in the corresponding order to map them to the input variables. For example, calling is_power(16,4) will execute the function by mapping n=16 and power=4. Sometimes, it is useful to explicitly assign values to variables. This can be done using keyword arguments. To use a keyword argument, we plug a mapping <variable name> = <value> into the function.

For example, is_power(n=16, power=4) will explicitly map n=16 and power=4 and execute the function's code.

In [28]:
is_power(n=16, power=4)
Out[28]:
True

With keyword arguments, we do not need to enter the values in the same order that was used to define the function. That is, is_power(power=4,n=16) will give the same result, whereas is_power(4,16) would map n=4 and power=16.

In [29]:
is_power(power=4, n=16)
Out[29]:
True

For a more illustrative toy example:

In [30]:
def f(a,b,c):
    print(a + b + c)
In [31]:
f('Hello','Goodbye','!')

HelloGoodbye!
In [32]:
f(c='Hello',a='Goodbye',b='!')

Goodbye!Hello

When calling a function, inputs that we've not explicitly labeled as keyword arguments are called positional arguments. All positional arguments must come before any keyword arguments, and their ordering determines the mapping to the input variable names.

In [33]:
f('Hello', c='Goodbye', b='!')

Hello!Goodbye
In [34]:
f(c='Hello', 'Goodbye', '!')

  Cell In[34], line 1
    f(c='Hello', 'Goodbye', '!')
                               ^
SyntaxError: positional argument follows keyword argument

Default arguments¶

It often happens that we write a function that takes in an input variable that has a natural or typically useful value. For example, in our second project, we will want to be able to tell if a given integer is a square. That is, we will want to use the is_power function with power=2.

In situations like this, we can assign a default value to the input variable power when we define the function. To do so, we use the syntax def <some function>(<some variable>=<default value>):. Let's modify the is_power function to default to power=2:

In [35]:
def is_power(n,power=2):
    root_n = n**(1/power)
    if round(root_n)**power == n:
        return True
    else:
        return False

When a function is defined with default arguments, we can override them by supplying our own input value, or skip that input value and use the default.

In [36]:
is_power(9)
Out[36]:
True
In [37]:
is_power(16)
Out[37]:
True
In [38]:
is_power(5)
Out[38]:
False
In [39]:
is_power(9,3)
Out[39]:
False
In [40]:
is_power(27,3)
Out[40]:
True

Note: When defining a function that takes in several variables, any variables that have default values assigned must come after all variables that do not.

In [45]:
def f(a='Hello', b='Goodbye', c='!'):
    print(a + b + c)
In [46]:
f()

HelloGoodbye!
In [47]:
f('MTH337')

MTH337Goodbye!
In [48]:
f(c='MTH337')

HelloGoodbyeMTH337