# Multiple of prime p + multiple of (integer<p) = 1 proof?

• Jolb
In summary, the goal of the "Multiple of prime p + multiple of (integer<p) = 1 proof" is to show that for any prime number p and any positive integer less than p, there exists a multiple of p and a multiple of that integer that add up to the number 1. This proof is important because it helps us understand the relationship between prime numbers and integers, and has applications in number theory and cryptography. The mathematical concept behind this proof is the Euclidean algorithm, which states that for any two positive integers a and b, there exists a unique pair of integers x and y such that ax + by = gcd(a,b). This proof is used in cryptography to ensure the security of encryption methods by generating keys based
Jolb
Let p be a prime number and x be some positive integer less than p.

How do I prove that there exist integers a and b such that
1 = ax + bp

Hint: compare what you have with what you need.

Since any term less than p is relatively prime to p, and thus has a solution of 1; it is easy to choose a desireable case.

Last edited: