algebra

[lusty finch]

1. Wait patiently for a helper to come along.
2. Once someone helps you, say thank you and close the thread with:

+close

3. Feel free to nominate the person for helper of the week in #helper-nominations
4. Do not ping the mods, unless someone is breaking the rules.
5. If you're happy with the help you got here, and the server overall, you can contribute financially as well: https://www.patreon.com/mathsdiscord

[stoic ruin]

mathgrinder

[pastel depot]

Hmm maybe try using modular arithmetics, you know (n-1)!+k is divisible by n thus (n-1)! Is congru -k modulo n, and I didn’t search further because I don’t have any paper nor pen but it’s good to think about

[pastel depot]

Well I’m not sure if it helps but if (n-1)! +k is divisible by n that means that (n-1)!+k is congru 0 modulo n that means the rest of the Euclidean division of (n-1)!+k by n is 0 thus (n+1)! Is congru -k modulo n

[left jewel]

What's the answer? I think a good thing to note is that, for $n>4$, \ \ I. If $n$ is prime, $(n-1)! \equiv (n-1) \pmod{n}$ \ \ II. If $n$ is composite, then $(n-1)! \equiv 0 \pmod{n}$

[stoic ruin]

civil_service_pigeon

[left jewel]

Wilson’s Theorem

[compact beacon]

if n | (n-1)! + k,
(I) if n is prime, n | (n-1) + k
(II) if n is composite, n | k

ah, there is a way to do this without bashing out all values of f
wait, not quite

pretty cool problem

[compact beacon]

yes

you can also simplify the first one

n | n - 1 + k

->

n | k - 1

so, now we can make a phrasing of f(k)

"f(k) is the prime factors of k - 1 plus the composite factors of k"

do you understand that

oh and we also have to account for n = 1, 2, 3, 4

ok
so

[compact beacon]

look at this image

if n | (a + c), and a is congruent to b mod n, then n | (b + c)

that justifies doing this
if n is prime > 4, n | (n-1)! + k implies n | (n-1) + k

so we get from n | (n-1)! + k to n | k - 1

iff n is prime

and n | (n-1)! + k to n | k, iff n is composite and at least 6

wait, idk if i believe that

ah yes no i believe that

because n === (n-1)!

as (n-1)! contains all the factors of n

somewhere in there

correct

if n is prime, there is definitely no n in there

[compact beacon]

so, we have f(k) is:
the prime factors of k - 1
+
the composite factors of k that are at least 6
+
possibly 1,4

as f(k) is just counting the n's that work

they are definitely going to come from 1 of those 3 sources

for prime n, again, n | k - 1, we already justified

so if n is prime it is a factor of k - 1

and since f is just counting the n's that work..

you see why the number of prime factors of k - 1 is added in

composite factors of k that are at least 6 also gets added in

it's not just

you also have some other things

[compact beacon]

.

it's either got to be a prime factor of k - 1, a composite factor of k at least 6, or 1, or 4, and those are all disjoint, so we can add them up

well, this is the trick

[compact beacon]

in fact, can you figure out when 1 and/or 4 is a value of n

yep

so the total increases by 99 just from the 1's, and by one when k is 2,6,10,...98

from the 4s

yes

what overlap

no

yes

from k = 6

f(6) would include both a +1 from the 1 and a +1 from the 4

so f(6) is at least 2

f(k) counts the n that work
it's ok if multiple n work

for 1 value of k

at this point i tbh do not know a better way to find the sum f(2) + ... + f(100) than going through all the prime numbers 2,3,5,7... and finding out how many k values have that prime as a factor of k - 1

and then going through all the composite numbers as well

6,8,9,10...

f(k) is the number of prime factors of k - 1 + the number of composite factors of k that are at least 6 + possibly 1,4

originally i thought "wow, you can just count the number of factors of 3 + the number of factors of 4 + ... "

but there is not an easy way to do that

lets take the example of n = 3

what values of k does that work for

yes

4, 7, ... 100

you can find how many there are

you can do that for 2, 3, 5, 7, 11, 13,

sounds like a pain but fortunately the values get small fast

then you would have to do the composite numbers as well

if you want to wait for someone else to arrive in the help channel

who has an idea to speed things up

that might be a good idea