How to solve prime factorization! Introducing an innovative solution

Hello. This is Tenmei Watanabe from Seito Medical School. This time we will talk about the method of prime factorization.

I would like to factorize 2521×2411=6078131 into prime factors. First of all, since prime number x prime number, prime numbers are always odd, except for 2, which is an even prime number. In other words, prime number x prime number is odd number x odd number.

Now, suppose we represent one prime number as 2a+1 and another prime number as 2b+1. In other words, one method of prime factorization is to solve for a and b of (2a+1)x(2b+1)=6078131. Expanding this formula, 4ab+2a+2b+1=6078131 and 2ab+a+b=3039065.

Now, I would like to use a remainder operation called mod. How to use 1mod2 means that when you divide a number by 2, the remainder is 1. For example, 3=1mod2, 7=1mod2, -1=1mod2.

In 2ab+a+b=3039065, 2ab on the left side is an even number, so the remainder when divided by 2 is 0mod2. The problem is a+b, and if a is odd and b is odd, then 1+1=0mod2, and if a is even and b is even, then 0+0=0mod2. On the other hand, if a is an even number (odd number) and b is an odd number (even number), then a+b=1+0=0+1=1mod2.

In other words, if a and b are each divided by 2, if the remainders are the same, they will add up to an even number, that is, 0mod2, and if a and b have different remainders, then they will add up to an odd number, i.e. It means that it becomes 1mod2.

Since 3039065=1mod2 on the right side, we can see that a+b=1mod2. In other words, if a is an odd number, then b is an even number.

Here, we want a+b=0mod2, so let's subtract 1 from a in the previous equation. In other words, a-1=c, and substitute a=c+1. (2(c+1)+1)x(2b+1)=(2c+3)x(2b+1)=6078131.2cb+b+3c=3039064.

Here, b+3c are even numbers or odd numbers, so 3039064=0mod2 on the right side. Now, let's add the coefficients of cb, b, and c. 2+1+3=6.

If you do 3039064mod6, you get 4mod6, and subtracting this 4 from 3039064 again and doing mod(6×2) is 0mod12, so you can see that a and b are both even numbers.

Because c=b=0, 2cb+c+b=2x0x0+0+0=0mod12=0mod24. Because c=b=1, 2x1x1+1+1=6mod12=6mod24. Furthermore, c=b=2, 2x2x2+2+2=12mod24, c=b=3, 2x3x3+3+3=0mod24.

In fact, 2c+3=2411,c=1204=0mod2. On the other hand, 2b+1=2521, b=1260. In other words, c=2d=0mod2, b=2e=0mod2.

Shall we do this two more times?

Substituting 2d and 2e for c and b, respectively, gives (4d+3)x(4e+1)=6078131. When expanded, it becomes 4de+d+3e=1519532. 1519532=0mod2, so d and e become d=e=0mod2 or d=e=1mod2.

The coefficients of de, d, and e are 4+1+3=8, so 1519532=4mod8=12mod16. (12-4) Since mod16=8mod16, we know that d=e=1mod2. d=e=1mod2 is incorrect because 4d+3=2411, d=602=2f=0mod2 and 4e+1=2521, e=630=2g=0mod2.

The next round is (8f+3)x(8g+1)=6078131. When expanded, 8fg+f+3g=759766=0mod2. Since f=g=0mod2 or f=g=1mod2, the coefficient is 8+1+3=12. Since 759766=10mod12=22mod24, (22-10)mod24=12mod24, and f=g=1mod2.

In fact, f=301=2h+1=1mod2, g=315=2i+1=1mod2, which is correct. I'd like to try it one more time quickly.

(16h+11)x(16i+9)=6078131。16fg+9f+11g=379877=1mod2。j=i-1。i=j+1。(16h+11)x(16j+25)=6078131。16hj+25h+11j=379866。

h+j=0mod2.16+25+11=52.379866=6mod52=58mod104. (58-6)=52mod104. h+j=1mod2. h=150=0mod2 ,j=156=0mod2 is incorrect.

Here, (16h+11)x(16i+9)=6078131 which was incorrect earlier, k=h-1, h=k+1. (16k+27)x(16i+9)=6078131.16ik+27i+9k=379868=0mod2.

i+k=0mod2.16+27+9=52.8mod52=60mod104. (60-8)=52mod104. i=k=1mod2.16k+27=2411, k=149=1mod2.16i+9=2521,i=157=1mod2. Therefore, it is correct.

(4d+3)x(4e+1)=6078131。d=s+2,e=t+2。(4s+11)x(4t+9)=6078131。4st+9s+11t=1519508。4+9+11=24。1519508=20mod24=20mod48。(20-20)mod48=0mod48。s=t=0mod2。s=600=0mod2。t=628=0mod2。

It seems important to do the math.