proving phi

[manic dagger]

Prove that if a positive integer p is the product of two distinct primes k and
j, then ϕ(p) = (k − 1)(j − 1).

[left sky]

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:

[manic dagger]

i just manged to write
p = kj
ϕ(p) = (k − 1)(j − 1)
ϕ(p) = kj -k-j+1
ϕ(p) = p-(k+j)+1

[next prism]

remember that j and k are prime

and the phi function returns how many numbers are coprime to a certain n and are smaller than that n

[manic dagger]

wait

[next prism]

now, a prime number has only 2 factors, 1 and itself
so it's GCD with any natural number smaller than it must be 1.
and there are n-1 natural numbers smaller than a given natural number n

[manic dagger]

i think i got it

[next prism]

also, phi(nm) = phi(n)*phi(m)

there's a proof for that too, but it's on wiki and I do not understand the wiki

i can send the page here though

[manic dagger]

is this a proof ?

[next prism]

no unfortunately

[manic dagger]

yeah

[next prism]

you'll have to state it mathematically

what I posted is the logic

[manic dagger]

i get the logic

[next prism]

idk how to frame that in hieroglyphics

so, you basically have to prove that

$\phi(p) = p-1$ if p is prime

$\phi(mn) = \phi(m)\phi(n)$

[glacial dragon]

No Lifer #GTFOanemia

[next prism]

first one is pretty easy i think
just use the definition of the phi function

[manic dagger]

btw

[next prism]

$\phi(k) = k\prod_{p|k}\qty(1-\frac{1}{p})$

[glacial dragon]

No Lifer #GTFOanemia

[manic dagger]

k+j = the number of integers that have a GCD > 1

[next prism]

?

[manic dagger]

try it with 3 and 7

or 3 adn 5

[next prism]

i don't get you

er

[manic dagger]

3x7 =21

[next prism]

oh like that huh

ok

[manic dagger]

we have 3, 6, 7 ,9,12,14,15,18,21

i was thinking of applying the inclusion-exclusion principle

[next prism]

inclusion exclusion

hmmm

go for it!

[next prism]

now if k is prime, its only prime divisor is itself

so the pseudo-infinite product simplifies down to

$\phi(k) = k\qty(1-\frac{1}{k})$ if k is prime

[glacial dragon]

No Lifer #GTFOanemia

[next prism]

$\phi(k) = k-1$ if k is prime

[glacial dragon]

No Lifer #GTFOanemia

[manic dagger]

i just need to prove the first one really

[next prism]

i just did that