# Modulo arithmetic and factoring n

• Mar 17th 2011, 06:53 PM
chrisc
Modulo arithmetic and factoring n
Hi again.
Its getting late and its been a long day. I have one more question to study before I call it.
Normally I would include my attempts on a question. But honestly, this time I do not think they are worth it. I feel lost on this one.
Luckily I found the question on the web so I can refer to it easily

http://www-users.math.umd.edu/~lcw/456F09.pdf
It is #3.

If this helps, this is listed under RSA questions.

Even if someone can supply direction or hints, I can try looking at it again in the morning.
Seeing that 1 there makes me want to say something related to Fermat's Little theorem, or at least a generalization of it.
• Mar 17th 2011, 07:29 PM
tonio
Quote:

Originally Posted by chrisc
Hi again.
Its getting late and its been a long day. I have one more question to study before I call it.
Normally I would include my attempts on a question. But honestly, this time I do not think they are worth it. I feel lost on this one.
Luckily I found the question on the web so I can refer to it easily

http://www-users.math.umd.edu/~lcw/456F09.pdf
It is #3.

If this helps, this is listed under RSA questions.

Even if someone can supply direction or hints, I can try looking at it again in the morning.
Seeing that 1 there makes me want to say something related to Fermat's Little theorem, or at least a generalization of it.

(a) Since $1\neq k^2=2^{n-1}$ , if n were a prime we'd be contradicting flt;

(b) With $x\in\mathbb{Z}\,,\,\,xn+1=k^2=2^{n-1}\Longrightarrow xn=2^{n-1}-1$ , and this is as far as I can get.

Tonio
• Mar 17th 2011, 07:42 PM
chrisc
thank you. ill take a look in the morning and see what I can do with b.
• Mar 21st 2011, 06:31 AM
chrisc
(k^2) - 1 = 0modn
(k+1)(k-1) = 0modn
but k =/= + 1 or -1
so there is a factor of n that divided (k+1) or (k-1)

find the gcd of (k-1, n)