Explore BrainMass

# Cryptography, congruences, and primes

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Hi,

Can you help me with these questions?

Consider the set of all even integers 2Z=....If this factorization into primes can be accomplished, is it unique? (see attached)

© BrainMass Inc. brainmass.com March 4, 2021, 9:24 pm ad1c9bdddf
https://brainmass.com/math/number-theory/cryptography-congruences-primes-241057

#### Solution Preview

Part I: Prime Numbers
(a) By the definition, all the primes in is , which is the set of the multiplications of 2 and an odd integer.
(b) Yes. We know, each even positive integer can be expressed as , where is an odd integer and . Since and , then we have
, the multiplication of 2's and .
So each even positive integer can be expressed as a product of these primes.
(c) This factorization is not unique.
Here is a counter example. Let , then we have
and
So has two ways to be expressed as the product of primes.

Part II: Congruence
Problem #7
Proof: If is a perfect square, then , then (mod 5). But we can go through all residues in modulo 5 and find that is not a quadratic residue. Therefore, (mod 5) has no solutions. This is a contradiction.
Hence can not be a perfect square.

Problem #46
in ...

#### Solution Summary

This provides examples of working with factorization into primes of even integers, proving an integer of a given form is not a perfect square, modular arithmetic, and RSA ciphers.

\$2.49