This work is concerned with probabilistic concepts of ’randomness’ and ‘independence’ relevant to classical number-theoretic problems. Basic properties of divisibility for natural numbers are interpreted in terms of probability spaces and appropriate probability distributions on classes of congruence. We analyze and demonstrate the importance of Zeta probability distribution, proving that probabilistic independence of coprime factors for randomly chosen natural numbers is equivalent to the fact that a random variable representing these numbers must follow Zeta probability distribution. We show that the probabilistic Cramér’s model for the asymptotic distribution of primes is validated by the proven here its asymptotic equivalence to Zeta probability distribution, in agreement with the Prime Number Theorem. We prove the exact formula for a Zeta distributed random variable to represent a prime number. It is used to generate and analyze the corresponding multiplicative and additive random walks on semigroups generated by primes and natural numbers, respectively. We prove that Cramér’s model for the distribution of primes, modified as a generalized predictable non-stationary Bernoulli process with dependent terms is asymptotically a process with pairwise independent Bernoulli variables. Finally, we provide probabilistic proof of the Strong Goldbach Conjecture, by using the results described above.