Algorithmic and Elementary Number Theory

Department of Computer Science

Winter 2018

Ariel University

Course staff

Course Lecturer:
Dr. Elad Aigner-Horev

Lecturer office hours:
By appointment (via email)

Course TAs:
Mr. Bar Alon, Mr. Gil Levy, Mr. Doron Mor

TAs' office hours:
Contact each TA individually

About the course

A mandatory course for 1st year 1st semester undergraduate students with the CS program at Ariel University.

The course aims at exposing the students to the culture of 'rigorous mathematical proofs'.

Consult the course syllabus to learn about your obligations throughout the course and the composition of the final grade.

Course Notes

Much of the course follows these notes.

The course and the notes are not in 1-1 correspondence. Ask the course lecturer for specific details as to where the course and the notes differ.

If the notes are not enough for you please consult the course syllabus for additional references.

There is a Hebrew translation of reference [3] in the syllabus by the Open University. The English version of [3] has a large intersection with our course. We did not check the translation offered by the Open University and will not be held liable for any of its content. Use it at your own peril. To clarify even further, the notation and terminology and techniques we use in class and in the lecture notes override those used in the booklet of the Open University.

How to study for this course?

We strongly recommend maintaining your own notes and not relaying on the notes of any other student

Try to review the material of previous lectures, practical sessions, and relevant assignments as much as possible before coming to class or trying to solve the next assignment

You will gain much benefit from keeping a study journal (in addition to your lecture and session notebooks) where you should attempt at proving the material seen in class and the assignments on your own.

Feel free to come see any of us during office hours


We strongly recommend that you study the whole semester and not only for the exams in this course.

We strongly advise you not to memorise exams from previous years or their solutions. We make a serious effort to change format and style (and obviously the content) of the final exams every course instance to counter as much as possible memorisation of exams.

Exams from previous course instances pose no binding obligations on the finals of this course instance.

In the last lecture the structure of both finals will be outlined to you in class

Assignments: regulations

Assignments in the course are not mandatory; we leave it to you to decide whether these are at all relevant to you. We strongly advise that you take the time to solve the assignments and/or study their published solutions.

The working assumption is that everybody is pursuing these assignments with full rigour.

If you wish to get feedback on your work please first consult the published solution and afterwards set an appointment with one of the TAs or the lecturer

Assignments in the course constitute the bare minimum one is expected to undergo. You are hereby strongly encouraged to go well beyond these. You can find exercises with solutions in the course lecture notes. Alternatively you can engage books listed in the course syllabus.

Assignments: links

Here are the links to the course assignments. These will be updated as the course progresses.

Assignment 1: Please try to read lecture 1 in the course lecture notes up to section 1.3 not including. Try to solve exercises 1-9 which are listed in section 1.4 (solutions can be found in section 1.5)

Assignment 2: Please try to read sections 2.1 and 2.2 in lecture 2 in the course lecture notes.

Assignment 3: Please try to solve all the exercises in lecture 2 in the course notes.

Assignment 4: Please try to read Lecture 5 in the course lecture notes

Assignment 5: Please try to solve all exercises in Lecture 5 in the course lecture notes

Assignment 6: Please try to read sections 6.1 (not including subsection 6.1.3), 6.2.1, 6.2.3, 6.3,6.4, 6.6

Assignment 7: Please try to read Lecture 7 in the notes and solve all exercises in that lecture

Assignment 8: Please try to read Lecture 8 in the notes and solve all exercises in that lecture

Assignment 9: Please try to read Lecture 9 in the notes and solve all exercises in that lecture

Assignment 10:
Assignment 11:
Assignment 12:
Assignment 13: TBA