What Are the Surrogate Number Congruences for Moduli Other Than Its Factors?

  • Thread starter Thread starter numbthenoob
  • Start date Start date
  • Tags Tags
    Factoring
numbthenoob
Messages
10
Reaction score
0
Let T represent an odd target number to be factored. Let m represent any odd number > 1.

If T is congruent to zero mod m, (T-1)/2 is congruent to (m-1)/2 mod m, and vice-versa.

For example

T
35 = 0 mod 5, 17 = 2 mod 5
77 = 0 mod 7, 38 = 3 mod 7
77 = 0 mod 11, 38 = 5 mod 11
47 = 0 mod 47, 23 = 23 mod 47
81 = 0 mod 3, 40 = 1 mod 3
81 = 0 mod 9, 40 = 4 mod 9
81 = 0 mod 27, 40 = 13 mod 27

and so on...

It's easy to see why; for any odd number divisible by another odd number, the halfway point through the dividend is going to correspond to the halfway point through the divisor's middle length.

My question is, what's up with the target number's congruences for moduli other than its factors?

35 = 2 mod 3, 17 = 2 mod 3

2 is one more than (3-1)/2, so wouldn't you expect 35 to be congruent to 1 mod 3? I would, I mean, it's necessarily congruent to zero when 17 is congruent to a number that's zero more than (m-1)/2...so, what am I missing?

Any help here would be greatly appreciated. Thanks.
 
Physics news on Phys.org
hi numbthenoob! :smile:

mod 5: 35 = 0, so 34 = 0-1 = 5-1 = 4, so 17 = (5-1)/2

mod 3: 35 = 2, so 34 = 2-1 = 1, so 17 = (2-1)/2 = 2

mod 11: 35 = 2, so 34 = 2-1 = 1, so 17 = (2-1)/2 = 6
 
Hi Tim, thanks for the reply.

Would you mind elaborating a little more on your remarks? I'm not seeing how (2-1)/2 equals 2 for mod 3 and 6 for mod 11. Doesn't it equal one half?

Or are you saying that in order to derive a remainder for m for 2x+1 from x, you double the remainder m leaves for x and add one?

i.e.
35 = 8 mod 9

because 17 = 8 mod 9
and 8*2 = 16, which is congruent to 7 mod 9
therefore 34 = 7 mod 9 and 34+1 = 7+1 mod 9

Is this what you were getting at and/or the correct understanding of how these remainders relate to one another?

Thanks, and sorry for being so dense.
 
hi numbthenoob! :smile:
numbthenoob said:
Would you mind elaborating a little more on your remarks? I'm not seeing how (2-1)/2 equals 2 for mod 3 and 6 for mod 11. Doesn't it equal one half?

you're not allowed fractions in mod arithmetic …

everything is whole numbers

so in mod 10, for example, 2x8 = 6, 3x8 = 4, 4x8 =2 and so on :wink:

and in mod 3, 2x2 = 1, so 1/2 = 2

and in mod 11, 2x6 = 1, so 1/2 = 6 :smile:
 
Oh, okay. Awesome, thanks.
 
##\textbf{Exercise 10}:## I came across the following solution online: Questions: 1. When the author states in "that ring (not sure if he is referring to ##R## or ##R/\mathfrak{p}##, but I am guessing the later) ##x_n x_{n+1}=0## for all odd $n$ and ##x_{n+1}## is invertible, so that ##x_n=0##" 2. How does ##x_nx_{n+1}=0## implies that ##x_{n+1}## is invertible and ##x_n=0##. I mean if the quotient ring ##R/\mathfrak{p}## is an integral domain, and ##x_{n+1}## is invertible then...
The following are taken from the two sources, 1) from this online page and the book An Introduction to Module Theory by: Ibrahim Assem, Flavio U. Coelho. In the Abelian Categories chapter in the module theory text on page 157, right after presenting IV.2.21 Definition, the authors states "Image and coimage may or may not exist, but if they do, then they are unique up to isomorphism (because so are kernels and cokernels). Also in the reference url page above, the authors present two...
I asked online questions about Proposition 2.1.1: The answer I got is the following: I have some questions about the answer I got. When the person answering says: ##1.## Is the map ##\mathfrak{q}\mapsto \mathfrak{q} A _\mathfrak{p}## from ##A\setminus \mathfrak{p}\to A_\mathfrak{p}##? But I don't understand what the author meant for the rest of the sentence in mathematical notation: ##2.## In the next statement where the author says: How is ##A\to...
Back
Top