Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °
You are not logged in.
Post a reply
Topic review (newest first)
I've never heard of the totient function before, but it seems like it's meant to be used to find an estimate. I think it takes the prime factors of N, divides does 1-(1/p) for each of them and multiplies all of those values together. That would give the proportion of all numbers that don't share factors with N, and so then you would multiply that value by Q to get the number of numbers less than or equal to Q that fits that description. It's only an estimate because the numbers are irregularly distributed when there is more than one prime factor. e.g N=12, Q=14, xxxx5x7xxx11x13x. However, when dealing with big numbers such as the ones you have given, the inaccuracy is much less.
a^p=a (mod p)
say Q = 1800598484394 and N = 18394394384
So, the problem may be approached this way:
The only way I can think of is, like eleusis said, a program.
The best primality test that I know is a small program that tests all numbers less than or equal to √x where x is the prime number that you are looking for. When you start testing numbers over 200 digits long then you start to run into the problem of finding a solution in this lifetime. There are other methods for finding prime numbers, like counting by primes to cut down on cycles, but I trust the brute-force all inclusive method and have never really needed to calulate primes greater than 50 digits.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
how do I find out how many numbers that have no common divisors with N and are smaller or equal to Q are there?