In this post, we work on a primality testing exercise obtained by altering one digit of a known large prime number. The idea is that we take a known large prime number, change one of the digits and test the primality of the resulting number. In this post, we use the smaller prime factor of the number that is known as RSA100. The goal is to keep changing digits (one at a time) until we obtain a prime number.
RSA100 is the smallest RSA number. It is a 330bit number (has 100 decimal digits). It was factored in 1991. The following are RSA100 and its two factors.

RSA100
15226050279225333605356183781326374297180681149613
80688657908494580122963258952897654000350692006139
Prime Factors of RSA100
37975227936943673922808872755445627854565536638199
40094690950920881030683735292761468389214899724061
The exercise is to alter one digit of the smaller factor until we get a prime number. Each position of can be altered in 9 different ways. For example, the leading digit of can be changed to 0,1,2,4,5,6,7,8,9. The leading digit being changed to 0 has the effect that the leading digit is truncated (the resulting number is a 49digit number).
___________________________________________________________________
The approach we take
Our approach is to work on one digit (position) of at a time. Once we pick a position, we examine the 9 different resulting numbers. For each of the 9 numbers, we perform the following three quick checks for compositeness.
 Check the sum of the digits. If the sum is divisible by 3, then the number is divisible by 3.
 Look for small prime factors.
 If is the number being tested, calculate . If it is not congruent to 1, we know is composite.
If any one of the checks turns up composite, we move on to another one of the 9 numbers. If all three checks fail to turn up composite, then we perform the Fermat primality test on that number. On the other hand, if all 9 numbers are found to be composite by the quick checks, then we pick another position and perform the same procedure.
___________________________________________________________________
The connection with weakly prime numbers
It is not entirely clear that the exercise of altering one digit of the smaller factor of RSA100 will eventually produce a prime number. In fact, there are prime numbers such that altering one digit will always produce a composite number. Such prime numbers are called weakly prime numbers. So the exercise we propose is to find out whether , the smaller factor of RSA100, is a weakly prime number. Our hope is that is not weakly prime. If one is patient and has a calculator that can work with large numbers, the answer will eventually be found. The number has 50 digits. So there are 450 numbers to check. However, we hope that a prime number will emerge long before having to check the 450th number.
The first few weakly prime numbers are 294001, 505447, 584141, 604171, 971767, 1062599.
___________________________________________________________________
The first iteration
Our first iteration is on altering the first digit (the leading digit) of . We have the following 9 numbers as a result.

07975227936943673922808872755445627854565536638199
17975227936943673922808872755445627854565536638199
27975227936943673922808872755445627854565536638199
47975227936943673922808872755445627854565536638199
57975227936943673922808872755445627854565536638199
67975227936943673922808872755445627854565536638199
77975227936943673922808872755445627854565536638199
87975227936943673922808872755445627854565536638199
97975227936943673922808872755445627854565536638199
The first check shows that , and are divisible by 3. Their sums of digits are 264, 267 and 270, respectively. We can rule out these three numbers. We then divide each remaining number by primes up to (and including) 97. We find that , and have small factors. Here are their factors:

: 59
: 7, 23
: 7
The remaining numbers are , and . We then compute the modular exponentiation in the third check. Here are the results:
where

15312755671443520117479645349899406067694314394411
28479886991585882317542223278882664321705349083600
73062611017560045453228840468835363523125806596486
Clearly are not 1. Thus , and are all composite. The first iteration yields no prime number.
___________________________________________________________________
Another 2 iterations
Next we choose to alter the second digit (the digit right after the leading digit). By applying the same procedure as for the first iteration, we find that all 9 resulting numbers are composite.
Unwilling to go with the natural order (3rd position, 4th position and so on), we choose the 27th position as the next iteration, 27th counting from the leading digit of . The following are the resulting 9 numbers:

37975227936943673922808872055445627854565536638199
37975227936943673922808872155445627854565536638199
37975227936943673922808872255445627854565536638199
37975227936943673922808872355445627854565536638199
37975227936943673922808872455445627854565536638199
37975227936943673922808872555445627854565536638199
37975227936943673922808872655445627854565536638199
37975227936943673922808872855445627854565536638199
37975227936943673922808872955445627854565536638199
The first check shows that , and are divisible by 3. Their sums of digits are 261, 264 and 267, respectively. These 3 numbers , and are out. Now look for small factors in the remaining numbers. Divide each of the remaining numbers by small primes up to (and including) 97. Small factors are found for three of them. They are:

: 11,47
: 53
: 17,59
The remaining numbers are , and . We then compute the modular exponentiation in the third check. Here are the results:
where

1
31019660101262614516708618435524184824189933761142
1
We have some interesting results by going to the 27th position. We have two numbers and that pass the three quick checks. These two numbers could still be composite. It could be that they have large factors that we have not detected. Or they have slightly larger Fermat witnesses that we have not yet found. We hope to settle these issues by applying a more formal primality test.
___________________________________________________________________
Checking for more evidence of primality
We wish perform primality testing on the number , the result of altering the 27th digit of the smaller factor of RSA100 to the digit of 1.
37975227936943673922808872155445627854565536638199
Before starting the Fermat test, we want to get further indication that is a prime. A quick check is to calculate for a few more small values of . In addition to that is done earlier, we have the following results:
So far so good. The Fermat congruence for the first 10 prime numbers indicates that may be a prime number. Some authors would stop at this point and declare that the number is prime. However, to minimize the chance of making a mistake (incorrectly identifying a composite number as prime), the values of should not be predetermined and should instead be randomized.
In any case, all the initial checks turn up no evidences that rule out primality for the number . We now continue with a randomized implementation of the Fermat test.
___________________________________________________________________
Fermat primality test
The Fermat test works the same as in the previous section, namely to calculate for more values of , except that the values are randomly selected. The following are 20 randomly selected values of where .

19849739905437652815437678431952000620013520723731
02124276794830381221643338971178300629602794570271
27138338415093662342987393979107100898152383178397
13439777399911226335368624024992520689134572541207
01296006449462468637265152716377285959118357948169
20162901028688646970889573834289207734216891750121
03158607876714769183179564222230937245373436521359
30367913460183037149800174337058220412636222780561
15671981166110368241285379979766798117058521736203
14484893059068285540085412541574057797151560108393
21310376560387253850314186514429075431358988956999
31751454532665167603222246950084316105718129864549
12514298198917547852874631789610584090955520049889
08879322212206875977179894330835479198484315727961
20439695787852522809810248767583601392695571172943
29336177583771558238055157728918246512748423397641
02964636742094604954001519522087518508106912037771
29924256551844529306459072702391350518242680154271
02316074815801009414245056557583330897320746154349
27750598271901581943312128958104515130586720939689
To use the Fermat’s little theorem, we need to check that each one of these values of is relatively prime to the modulus . We use the Euclidean algorithm to compute for all . The results are:
Each random number is relatively prime to the number . This provides another check. If any of the GCD is greater than 1, then we would have found divisor of that is greater than 1, in which case the primality test will be aborted.
Now we proceed to calculate . If any one of these congruence values is not 1, then we declare that is composite. If all 20 congruence values are 1, then we declare that is a prime number. The following table shows the results.
The Fermat test results, both the predetermined part with the first 10 prime numbers and the randomized part with the 20 random selections, show that we have very strong evidence that the number is a prime number. All together, we have shown that for 30 values of , 20 of which are randomly selected in the interval .
Recall Fermat's little theorem, which states that if is a prime number, then for all integers relatively prime to the modulus .
With being true for 30 values of relatively prime to , if we declare that is prime, what is the probability of making a mistake? Put another way, if is really a composite number, what is the probability of getting for 20 random choices of ? The probability is practically zero, except for one caveat. Thus we declare that is a prime number with the one caveat discussed below.
___________________________________________________________________
Remarks
There are composite integers such that for every integer that is relatively prime to . These composite integers are called Carmichael numbers. The smallest Carmichael number is 561 (with factors 3, 11, 17).
The Fermat test will always declare a Carmichael number as prime. In other words, the Fermat test will always give a false positive if the test is applied on a Carmichael number. Fortunately Carmichael numbers are rare. So when the number whose primality is being tested is randomly selected, the Fermat test will often give the correct result. Selecting a number at random, it is not likely to pick a Carmichael number. But the number is not obtained by random selection. It is obtained in a predetermined way (by altering one digit of a known prime number).
So if you have a nagging worry that the number might be a Carmichael number, the MillerRabin test should be used instead. Carmichael numbers will not evade the MillerRabin test. When applying the MillerRabin test on a composite number (Carmichael number or not), it will detect the compositeness with arbitrarily small error probability.
The MillerRabin test is an extension of the Fermat test and has minimal additional calculation. We actually structure the calculation of in the above table with the MillerRabin test in mind. We find that the MillerRabin test also indicates that the number is prime. With the 20 random values of , the error probability is at most , which is for all practical purposes zero. In other words, if were a composite number, there would be a close to zero chance that MillerRabin test would make a mistake by declaring a prime number. With such a small error probability, we declare that the number is prime.
Tying back to the notion of weakly prime numbers, we have found a prime number by altering one digit of the prime number , the smaller factor of RSA100. Thus the prime number is not a weakly prime number.
___________________________________________________________________
Exercises
The number
37975227936943673922808872955445627854565536638199
,obtained by changing the 27th digit of the smaller factor of RSA100 to the digit of 9, is a probable prime (see above). Test the primality of this number.
Find another prime number by altering a different digit of .
Another possible exercise is to do the same exercise on the larger factor of RSA100 or factors of other RSA numbers.
___________________________________________________________________