🔢 Arithmetic in Zn

A C++20 implementation of arithmetic operations in Z_n originally developed for a university Algebraic Foundations of Computer Science seminar assignment and later refactored and expanded into a standalone project, featuring invertible element computation, linear congruence solving, Euler's totient function, modular exponentiation, Euler's theorem, prime factorization, and nilpotent element computation.

📖 Overview

This project was originally developed as part of the Algebraic Foundations of Computer Science university course as a seminar assignment focused on arithmetic and algebraic operations in the ring Z_n.

The project implements a collection of fundamental operations in Z_n, including determining invertible elements, solving linear congruences, computing modular powers, calculating Euler's totient function, prime factorization, and determining nilpotent elements.

The project was developed to practice and demonstrate fundamental Algebra and Number Theory concepts in C++, including modular arithmetic, greatest common divisors, invertibility in Z_n, Euler's theorem, Euler's totient function, prime factorization, linear congruences, and nilpotent elements.

The program reads the values a, m, and n, with n >= 2, validates the input, and performs the required operations in Z_n. The implementation uses the recursive Euclidean algorithm for computing the greatest common divisor and uses the result to determine whether elements are invertible modulo n.

The main functionality includes:

• input validation for a, m, and n
• greatest common divisor computation using the Euclidean algorithm
• determination of invertible elements of Z_n
• invertibility testing
• solving linear congruences of the form a * x ≡ m (mod n)
• handling equations with no solutions, one solution, or multiple solutions
• prime factorization
• Euler's totient function φ(n)
• modular exponentiation using Euler's theorem when applicable
• modular exponentiation using binary exponentiation when Euler's theorem cannot be applied
• determination of nilpotent elements of Z_n

A major focus of the project was implementing the fundamental arithmetic and algebraic operations in Z_n required by the original assignment. The implementation handles both invertible and non-invertible elements when solving linear congruences and distinguishes between cases where Euler's theorem can and cannot be directly applied.

For modular exponentiation, Euler's theorem is used when gcd(a, n) = 1. When this condition is not satisfied, the implementation uses binary exponentiation, providing a general and efficient method for computing a^m mod n.

The original seminar implementation was later refactored and modernized for GitHub, including clearer English naming, improved structure, input validation, explicit handling of special cases, cleaner console interaction, and more consistent implementations of the mathematical operations.

The final result is a standalone C++20 console application that demonstrates how fundamental algebraic concepts from Z_n can be implemented from scratch while applying mathematical algorithms such as the Euclidean algorithm, Euler's theorem, Euler's totient function, prime factorization, and binary exponentiation.

📚 Original Assignment

The project was originally developed as part of the university Algebraic Foundations of Computer Science course as a seminar assignment focused on arithmetic and algebraic operations in the ring Z_n.

The assignment requires reading natural numbers a, m, and n, with n >= 2, and implementing several operations involving elements of Z_n.

1. Input

The program must read three natural numbers:

• a — the element/base used in the modular operations.
• m — the value used as the right-hand side of the congruence and as the exponent.
• n — the modulus, with n >= 2.

2. Invertible Elements

The program must determine the invertible elements of Z_n.

An element a belongs to the group of invertible elements of Z_n if and only if:

gcd(a, n) = 1

The program must display the set of invertible elements of Z_n.

3. Linear Congruence

The program must solve the equation:

a * x ≡ m (mod n)

The implementation must determine the solutions x belonging to Z_n.

Depending on the values of a, m, and n, the equation may have:

• no solutions
• one solution
• multiple solutions

4. Modular Exponentiation

The program must compute:

a^m mod n

using Euler's theorem.

When gcd(a, n) = 1, Euler's theorem states that:

a^φ(n) ≡ 1 (mod n)

where φ(n) is Euler's totient function.

The implementation therefore uses Euler's theorem when its conditions are satisfied.

5. Nilpotent Elements

The program must determine the nilpotent elements of Z_n.

An element x is nilpotent if there exists a positive integer k such that:

x^k ≡ 0 (mod n)

The program must display the set of nilpotent elements of Z_n.

6. Mathematical Concepts

The assignment provides practice with fundamental concepts from Algebraic Foundations of Computer Science, including:

• Modular arithmetic
• Greatest common divisor
• Invertible elements in Z_n
• Linear congruences
• Euler's theorem
• Euler's totient function
• Prime factorization
• Nilpotent elements

Together, these requirements define the complete functionality of the original seminar assignment and provide practical experience implementing fundamental algebraic operations in C++.

✨ Features

• 🔢 Arithmetic in Z_n

  • Custom implementation of fundamental arithmetic and algebraic operations in Z_n
  • Works with natural numbers a, m, and n
  • Validates input values and requires n >= 2
  • Uses long long integers for arithmetic operations

• 🔐 Invertible Elements

  • Determines all invertible elements of Z_n
  • Uses the condition gcd(x, n) = 1
  • Implements the recursive Euclidean algorithm for GCD computation
  • Displays the complete set of invertible elements

• 🔎 Invertibility Testing

  • Checks whether an element is invertible modulo n
  • Determines invertibility using the greatest common divisor
  • Correctly handles both invertible and non-invertible elements

• 🧮 Linear Congruence Solving

  • Solves equations of the form a * x ≡ m (mod n)
  • Searches for solutions directly within Z_n
  • Handles equations with no solutions
  • Handles equations with a unique solution
  • Handles equations with multiple solutions
  • Correctly handles the special case a = 0

• 🔢 Prime Factorization

  • Computes the prime factorization of n
  • Handles the factor 2 separately for efficient factorization
  • Tests only odd divisors after processing 2
  • Provides the prime factors required by other mathematical operations

• 📐 Euler's Totient Function

  • Computes Euler's totient function φ(n)
  • Uses the distinct prime factors of n
  • Applies the formula: φ(n) = n × ∏(p - 1) / p

• ⚡ Modular Exponentiation

  • Computes a^m mod n
  • Uses Euler's theorem when gcd(a, n) = 1
  • Reduces the exponent using φ(n)
  • Uses binary exponentiation when Euler's theorem cannot be applied
  • Correctly handles cases where a and n are not coprime

• 🧠 Euler's Theorem

  • Implements Euler's theorem for modular exponentiation
  • Applies the theorem only when gcd(a, n) = 1
  • Uses the relationship a^φ(n) ≡ 1 (mod n)
  • Simplifies modular exponentiation for large exponents

• 🌱 Nilpotent Elements

  • Determines the nilpotent elements of Z_n
  • Uses the distinct prime factors of n
  • Computes the product of the distinct prime factors
  • Displays all nilpotent elements belonging to Z_n

• 🔄 Greatest Common Divisor

  • Implements the recursive Euclidean algorithm
  • Used to determine whether elements are invertible
  • Used to decide whether Euler's theorem can be applied
  • Provides the mathematical foundation for several operations

• 🖥️ Interactive Console Application

  • Console-based user interface
  • Prompts the user for a, m, and n
  • Displays the results of all implemented operations
  • Provides clear messages for equations with and without solutions
  • Reports the computed modular arithmetic results directly in the console

• 🛡️ Input Validation

  • Rejects negative values for a
  • Rejects negative values for m
  • Requires n >= 2
  • Requests valid input again when an invalid value is entered

• 🧩 Edge Case Handling

  • a = 0
  • m = 0
  • a and n not being coprime
  • Linear congruences with no solutions
  • Linear congruences with multiple solutions
  • Prime values of n
  • Composite values of n
  • Cases where the only nilpotent element is 0

🏗️ Application Architecture

The application follows a simple functional architecture centered around independent functions that implement the mathematical operations required for arithmetic in Z_n.

The program is implemented as a single C++ source file, main.cpp, which contains the input handling, mathematical algorithms, modular arithmetic operations, and console output.

The implementation separates the different mathematical responsibilities into dedicated functions, making each operation independently identifiable and easier to understand.

                              main.cpp
                                 │
                                 ▼
                            readInput()
                                 │
                                 ▼
                        ┌─────────────────┐
                        │ Mathematical    │
                        │ Operations      │
                        └────────┬────────┘
                                 │
          ┌──────────────────────┼──────────────────────┐
          │                      │                      │
          ▼                      ▼                      ▼
        GCD                  Z_n Operations       Number Theory
          │                      │                      │
          ▼                      ├── Invertibility      ├── Prime Factorization
   gcdRecursive()               ├── Congruences        └── Euler's Totient
                                └── Nilpotents
          │
          ▼
   Euler's Theorem
          │
          ▼
   Modular Exponentiation
          │
          ├── gcd(a,n) = 1
          │       │
          │       ▼
          │   Euler's theorem
          │
          └── gcd(a,n) != 1
                  │
                  ▼
          Binary exponentiation

🧩 Main Components

• readInput()

  • Reads the values a, m, and n.
  • Validates the input values.
  • Requires n >= 2.
  • Rejects negative values for a and m.

• gcdRecursive()

  • Computes the greatest common divisor using the recursive Euclidean algorithm.
  • Provides the basis for determining whether an element is invertible.
  • Determines whether Euler's theorem can be applied to modular exponentiation.

• displayInvertibleElements()

  • Determines and displays the invertible elements of Z_n.
  • Uses the condition gcd(x, n) = 1.

• isInvertible()

  • Checks whether a specific element is invertible modulo n.
  • Uses the greatest common divisor to perform the check.

• findSolution() / findAllSolutions()

  • Search for solutions of the linear congruence a * x ≡ m (mod n).
  • Operate directly on the elements of Z_n.

• solveEquation()

  • Coordinates the solution of linear congruences.
  • Handles equations with no solutions, one solution, or multiple solutions.
  • Explicitly handles the special case a = 0.

• primeFactorization()

  • Computes the distinct prime factors of n.
  • Provides the factorization required by Euler's totient function and nilpotent element computation.

• eulerTotient()

  • Computes Euler's totient function φ(n).
  • Uses the distinct prime factors obtained from primeFactorization().

• modularPowerUsingEuler()

  • Computes a^m mod n using Euler's theorem.
  • Used when gcd(a, n) = 1.
  • Reduces the exponent using φ(n).

• modularPower()

  • Computes modular powers using binary exponentiation.
  • Provides a general solution when Euler's theorem cannot be applied.

• calculateModularPower()

  • Determines which modular exponentiation method should be used.
  • Uses Euler's theorem for coprime a and n.
  • Uses binary exponentiation otherwise.

• displayNilpotentElements()

  • Determines and displays the nilpotent elements of Z_n.
  • Uses the distinct prime factors of n to determine the required set.

• main()

  • Application entry point.
  • Reads the input values.
  • Executes all required mathematical operations.
  • Displays the results in the console.

📦 Functional Responsibilities

The functions in main.cpp are organized around several mathematical responsibilities:

• Input and Validation

  • Reading a, m, and n.
  • Validating the input constraints.

• Number Theory

  • Greatest common divisor.
  • Prime factorization.
  • Euler's totient function.

• Arithmetic in Z_n

  • Invertible element determination.
  • Linear congruence solving.
  • Nilpotent element determination.

• Modular Exponentiation

  • Euler's theorem.
  • Binary exponentiation.
  • Selection of the appropriate method based on gcd(a, n).

• Console Output

  • Displaying the computed sets and numerical results.
  • Reporting whether equations have zero, one, or multiple solutions.

🧠 Mathematical Dependencies

Several operations build upon the results of other functions:

gcdRecursive()
      │
      ├──────────────► isInvertible()
      │                       │
      │                       ▼
      │                 solveEquation()
      │
      └──────────────► calculateModularPower()
                              │
                    ┌─────────┴─────────┐
                    │                   │
              gcd(a,n) = 1       gcd(a,n) != 1
                    │                   │
                    ▼                   ▼
       modularPowerUsingEuler()   modularPower()
                    │
                    ▼
             eulerTotient()
                    │
                    ▼
          primeFactorization()

primeFactorization()
      │
      ├──► eulerTotient()
      │
      └──► displayNilpotentElements()

This dependency structure keeps the mathematical operations modular and easy to follow, with lower-level algorithms such as the Euclidean algorithm and prime factorization being reused by higher-level operations.

🔄 Application Flow

The application starts in main.cpp and executes the required operations sequentially:

main.cpp
    │
    ▼
Read and validate input
    │
    ▼
Display invertible elements
    │
    ▼
Solve linear congruence
    │
    ▼
Calculate a^m mod n
    │
    ├──► Euler's theorem when applicable
    │
    └──► Binary exponentiation otherwise
    │
    ▼
Display nilpotent elements
    │
    ▼
End program

This architecture keeps the implementation compact and focused, with each function responsible for a specific mathematical operation and main.cpp coordinating the complete execution of the console application.

📂 Project Structure

ArithmeticZn/
├── .gitignore
├── ArithmeticZn.slnx
└── ArithmeticZn/
    ├── ArithmeticZn.vcxproj
    ├── ArithmeticZn.vcxproj.filters
    └── main.cpp

Build artifacts, Visual Studio intermediate files, executables, debug databases, and other temporary files are excluded from version control through .gitignore.

🛠️ Built With

• C++20 (ISO C++20)
• Visual Studio 2026
• Microsoft C++ Build Tools v145
• 64-bit build
• std::vector for dynamic collections
• Recursive Euclidean algorithm
• Prime factorization
• Euler's theorem
• Euler's totient function
• Binary exponentiation
• Standard Streams for console input and output

⭐ Highlights

• 🔢 Arithmetic in Z_n

  • Custom implementation of fundamental arithmetic and algebraic operations in Z_n
  • Implements the main operations required by the original seminar assignment
  • Works with modular arithmetic using natural number inputs

• 🔐 Invertible Elements

  • Determines all invertible elements of Z_n
  • Uses the condition gcd(x, n) = 1
  • Implements the recursive Euclidean algorithm for GCD computation

• 🧮 Linear Congruence Solving

  • Solves equations of the form a * x ≡ m (mod n)
  • Searches directly through the elements of Z_n
  • Handles no-solution, unique-solution, and multiple-solution cases
  • Includes explicit handling of the a = 0 special case

• ⚡ Modular Exponentiation

  • Computes a^m mod n
  • Uses Euler's theorem when gcd(a, n) = 1
  • Calculates Euler's totient function φ(n)
  • Uses binary exponentiation when Euler's theorem cannot be applied

• 🌱 Nilpotent Elements

  • Determines the nilpotent elements of Z_n
  • Uses prime factorization to identify the required elements
  • Correctly handles both prime and composite moduli

• 🔢 Number Theory Algorithms

  • Recursive Euclidean algorithm
  • Prime factorization
  • Euler's totient function
  • Euler's theorem
  • Binary exponentiation
  • Modular arithmetic

• 🛡️ Robust Input and Edge Case Handling

  • Validates a, m, and n
  • Requires n >= 2
  • Handles a = 0 and m = 0
  • Handles non-invertible elements
  • Handles equations with no or multiple solutions

• 🖥️ Console Application

  • Simple interactive console interface
  • Clear prompts and formatted mathematical results
  • Displays all required results sequentially
  • No external libraries or dependencies required

• 🏗️ Refactored Implementation

  • English naming throughout the code
  • Consistent camelCase naming convention
  • Clear separation between mathematical operations
  • Improved input validation
  • Improved handling of special cases
  • Refactored and prepared as a standalone GitHub project

🎯 Concepts Demonstrated

• Modular Arithmetic

  • Arithmetic operations in the ring Z_n
  • Working with congruences modulo n
  • Reduction of values to their representatives in Z_n
  • Computation of modular powers

• Greatest Common Divisor

  • Recursive implementation of the Euclidean algorithm
  • Determining whether two integers are coprime
  • Using gcd(a, n) to determine invertibility
  • Using the GCD to determine whether Euler's theorem can be applied

• Invertible Elements in Z_n

  • Characterization of invertible elements using gcd(x, n) = 1
  • Determination of the complete set of invertible elements
  • Understanding the multiplicative group of units of Z_n

• Linear Congruences

  • Solving equations of the form a * x ≡ m (mod n)
  • Searching for solutions within Z_n
  • Handling equations with no solutions
  • Handling equations with a unique solution
  • Handling equations with multiple solutions

• Euler's Theorem

  • Application of Euler's theorem when gcd(a, n) = 1
  • Use of the relation a^φ(n) ≡ 1 (mod n)
  • Reduction of large exponents modulo φ(n)
  • Simplification of modular exponentiation

• Euler's Totient Function

  • Computation of φ(n)
  • Use of the distinct prime factors of n
  • Application of the formula: φ(n) = n × ∏(p - 1) / p
  • Integration with Euler's theorem

• Prime Factorization

  • Decomposition of an integer into its distinct prime factors
  • Efficient handling of the factor 2
  • Testing odd divisors for the remaining factorization
  • Reusing prime factorization in multiple mathematical operations

• Modular Exponentiation

  • Computation of a^m mod n
  • Euler-based exponent reduction for coprime values
  • Binary exponentiation for the general case
  • Efficient computation without constructing the full value of a^m

• Binary Exponentiation

  • Repeated squaring for modular powers
  • Reduces the number of multiplication operations
  • Works regardless of whether a and n are coprime
  • Provides a fallback when Euler's theorem cannot be applied

• Nilpotent Elements

  • Identification of nilpotent elements in Z_n
  • Understanding the condition x^k ≡ 0 (mod n)
  • Use of the distinct prime factors of n
  • Determination of the complete set of nilpotent elements

• Number Theory Algorithms

  • Euclidean algorithm
  • Prime factorization
  • Euler's totient function
  • Euler's theorem
  • Binary exponentiation
  • Modular arithmetic algorithms

• Mathematical Case Analysis

  • Coprime and non-coprime values of a and n
  • Prime and composite moduli
  • Equations with zero, one, or multiple solutions
  • Special case a = 0
  • Special case m = 0

• Input Validation

  • Validation of natural number inputs
  • Rejection of negative values for a and m
  • Enforcement of the condition n >= 2
  • Repeated input for invalid values

• Functional Decomposition

  • Each mathematical operation is implemented through a dedicated function
  • Lower-level algorithms are reused by higher-level operations
  • Mathematical dependencies are kept explicit
  • main() coordinates the complete sequence of operations

• Modern C++ Practices

  • C++20 language features and syntax
  • using int64 = long long for concise integer type declarations
  • std::vector for dynamically sized collections
  • Range-based for loops
  • const variables for values that should not be modified
  • nullptr and modern C++ syntax where applicable
  • Clear and consistent English naming
  • Consistent camelCase function naming

📊 Test Results

The Arithmetic in Z_n implementation was manually tested through the console application.

The testing covered the main functionality of the project, including:

• Invertible element computation
• Linear congruence solving
• Modular exponentiation
• Euler's theorem
• Euler's totient function
• Nilpotent element computation
• Input validation
• Special cases such as a = 0 and m = 0
• Cases with prime and composite moduli
• Cases where gcd(a, n) = 1 and gcd(a, n) != 1

✅ Tested Operations

Operation	Result
Invertible elements	Passed
Linear congruence with multiple solutions	Passed
Linear congruence with a unique solution	Passed
Linear congruence with no solutions	Passed
Modular exponentiation using Euler's theorem	Passed
Modular exponentiation with non-coprime values	Passed
Nilpotent element computation	Passed
Input validation	Passed
a = 0 special case	Passed
m = 0 special case	Passed
Prime modulus	Passed
Composite modulus	Passed

🔢 Test Case 1 — Composite Modulus

Input:

Enter the value of a: 2
Enter the value of m: 10
Enter the value of n: 8

Output:

The invertible elements of Z_8 are: {1, 3, 5, 7}.
The equation 2*x = 10 in Z_8 has the solutions x = {1, 5}.
The result of 2^10 % 8 is 0.
The nilpotent elements of Z_8 are: {0, 2, 4, 6}.

This test verifies:

• invertible elements in a composite Z_n
• a linear congruence with multiple solutions
• modular exponentiation when gcd(a, n) != 1
• nilpotent elements in Z_8

🔢 Test Case 2 — Prime Modulus

Input:

Enter the value of a: 3
Enter the value of m: 100
Enter the value of n: 7

Output:

The invertible elements of Z_7 are: {1, 2, 3, 4, 5, 6}.
The equation 3*x = 100 in Z_7 has the solution x = 3.
The result of 3^100 % 7 is 4.
The nilpotent elements of Z_7 are: {0}.

This test verifies:

• all non-zero elements being invertible in Z_7
• a linear congruence with a unique solution
• modular exponentiation using Euler's theorem
• the fact that 0 is the only nilpotent element when the modulus is prime

🔢 Test Case 3 — Non-Invertible Element

Input:

Enter the value of a: 4
Enter the value of m: 2
Enter the value of n: 6

Output:

The invertible elements of Z_6 are: {1, 5}.
The equation 4*x = 2 in Z_6 has the solutions x = {2, 5}.
The result of 4^2 % 6 is 4.
The nilpotent elements of Z_6 are: {0}.

This test verifies:

• invertible elements in a composite modulus
• a congruence with multiple solutions
• modular exponentiation when gcd(a, n) != 1
• nilpotent element computation

🔢 Test Case 4 — Zero Special Case

Input:

Enter the value of a: 0
Enter the value of m: 0
Enter the value of n: 5

Output:

The invertible elements of Z_5 are: {1, 2, 3, 4}.
The equation 0*x = 0 in Z_5 has all elements of Z_5 as solutions.
The result of 0^0 % 5 is 1.
The nilpotent elements of Z_5 are: {0}.

This test verifies:

• handling of a = 0
• handling of m = 0
• the special congruence 0*x ≡ 0 (mod n)
• modular exponentiation with exponent 0
• nilpotent elements for a prime modulus

🧮 Euler's Theorem Verification

The second test case also verifies the use of Euler's theorem.

For:

a = 3
m = 100
n = 7

we have:

gcd(3, 7) = 1
φ(7) = 6
100 mod 6 = 4

Therefore:

3^100 ≡ 3^4 ≡ 4 (mod 7)

which matches the program output:

The result of 3^100 % 7 is 4.

Result: All major operations required by the original assignment were manually verified through the console application. The tests cover prime and composite moduli, invertible and non-invertible elements, linear congruences with different numbers of solutions, modular exponentiation, Euler's theorem, nilpotent elements, and special cases involving zero values.

📋 Requirements

• Windows 10 / Windows 11
• Visual Studio 2026
• Microsoft C++ Build Tools v145
• C++20 (ISO C++20)
• 64-bit build environment

Developed and tested using Visual Studio 2026 with the Microsoft C++ Build Tools v145 toolset, C++20 (ISO C++20), and a 64-bit build configuration.

🚀 Running

1. Clone the repository.

git clone <repository-url>

2. Open ArithmeticZn.slnx in Visual Studio 2026.

3. Make sure the project is configured with:

• Microsoft C++ Build Tools v145
• C++20 (ISO C++20)
• 64-bit

4. Build the solution.

Build → Build Solution

or simply press:

Ctrl + Shift + B

5. Run the application.

F5

or click Start in Visual Studio.

🖥️ Console Application

When the application starts, it requests the three input values required by the assignment:

Enter the value of a: 
Enter the value of m: 
Enter the value of n:

The program validates the input and requires:

• a >= 0
• m >= 0
• n >= 2

After receiving valid input, the application automatically performs all required operations.

🔐 Invertible Elements

The program displays all invertible elements of Z_n.

For example:

Enter the value of a: 3
Enter the value of m: 100
Enter the value of n: 7

The invertible elements of Z_7 are: {1, 2, 3, 4, 5, 6}.

An element is considered invertible when its greatest common divisor with n is equal to 1.

🧮 Linear Congruence

The program solves the congruence:

a * x ≡ m (mod n)

For example:

The equation 4*x = 2 in Z_6 has the solutions x = {2, 5}.

The implementation handles equations with:

• no solutions
• one solution
• multiple solutions
• the special case a = 0

⚡ Modular Exponentiation

The program computes:

a^m mod n

When gcd(a, n) = 1, Euler's theorem is used to reduce the exponent.

For example:

The result of 3^100 % 7 is 4.

When Euler's theorem cannot be applied because gcd(a, n) != 1, the implementation uses binary exponentiation instead.

🌱 Nilpotent Elements

The program also determines the nilpotent elements of Z_n.

For example, for n = 8:

The nilpotent elements of Z_8 are: {0, 2, 4, 6}.

🔄 Program Flow

The application executes the operations sequentially:

Read a, m, n
      │
      ▼
Validate input
      │
      ▼
Display invertible elements
      │
      ▼
Solve a*x ≡ m (mod n)
      │
      ▼
Calculate a^m mod n
      │
      ├──► Euler's theorem
      │
      └──► Binary exponentiation
      │
      ▼
Display nilpotent elements
      │
      ▼
End

The application does not require any external dependencies or additional runtime configuration beyond the specified C++ development environment.

📄 License

This project is released under the MIT License.

See the LICENSE file for more details.