elementary-number-theory

[neat harness]

yes let y = a0 + nk

show y satisfies the ay=b mod n

what

[wheat patio]

does a(x0+nk) not distribute to a(x0)+a(nk)?

[neat harness]

It does

[wheat patio]

But that's not what I have

So I don't know how I could use that

[neat harness]

what is nk mod n

O nvm I misread,

What you have so far will just show it holds for some k from definition of divisibility

Your goal is to show it holds for all k

So you should adjust your approach

And I am suggesting you consider what a(x0 +nk) is for all integers k

[safe lake]

Hey dose any body need help here

[raven dagger]

how to find solutions to $2^x \equiv -x \pmod{13}$?

[sterile pumice]

silverwildflower8

[raven dagger]

i know how to find solutions if there isn't an x on the right side using indices

but im not sure how to apply those here

[weary rune]

the modulus is small enough here that you can probably just check all of them

[raven dagger]

is there any way to do it without checking all of them

[iron surge]

So first I was stumped with this but then I found the smallest natural number for which that congruence relation holds. That number is x=12. Then I note the remainders that powers of 2 cycle through (mod 13). 2^12 leaves a remainder of 1 and so 2^(12^k) leaves a remainder of 1 as well for all integers k>0. Now I must find when 12^k leaves a remainder of -1 so that 2^(12^k)+12^k is divisible by 13. Since 12 leaves a remainder of -1, it amounts to asking when (-1)^k leaves a remainder of -1? That of course is when k is odd. And you can check for urself and find that powers of 12 are either congruent to 1 or -1 mod 13 and they alternate -1,1,-1,1,.... So I have found infinitely many natural numbers x for which ur congruence relation holds. I will leave it up to you to determine if that is the only values of x for which the relation holds

[raven dagger]

ah that makes sense

thx

[iron surge]

ur welcome.

[placid linden]

let a,b,c,d be natural numbers. if ab = cd, then a = xy, b= zh, c = xz, y = yh

if i wanted to use this in an exam, what theorem would i quote?

[primal pewter]

I would rather prove it

[coral venture]

I know it as four number lemma

[sacred junco]

Why is it that the sum of the digits of primes never equals some number 3k , k>1

[primal pewter]

because otherwise the number would be divisible by 3

[neat harness]

(divisibilty rule for 3)

[sacred junco]

i see

thanks you both

[placid linden]

let a,b,c,d be natural numbers. if ab = cd, then a = xy, b= zh, c = xz, d = yh

does anyone have a simple proof for this ??

[astral verge]

let g = gcd(a, c)

then by the definition of greatest common divisor, there exist integers x and z such that a = xg and c = zg

since g divides both a and c

we have a = xg and c = zg for some integers x and z

substituiting into the equation ab = cd

(xg)(b) = (zg)(d)

cancelling g from both sides (since g is non-zero as it divides a and c)

xb = zd

and so on..

[raven dagger]

how to prove the change of base formula for indices in modulos

[quick furnace]

can you state the formula you're talking about?

[merry cradle]

what do I do if for the chinese rest theorem im working with non partly external mods
like I have mod 5, 6, 7, 8 and 9

[still flare]

I don't understand the question. Can you be more specific about the situation that you can't use the chinese remainder theorem with

[merry cradle]

so I have this system of mod x I need to solve for

they are in total 5

My problem here is that I have mod 5 mod 6 mod 7 mod 8 and mod 9 as the rings I am working with

but

8 6 and 9 6 are not partly external

I was thinking about finding the smallest common denominator but then Im not sure for what value of x Im supposed to solve for

And about the gdc well Im still not very sure, for 6 and 8 would work nicely with 1 mod 2, but with the 6 9 I am not sure

would be 0 mod 3

but is that it?

because If im working with now just mod 2, 3, 5 and 7

then everything changes

like Im pretty confused and trying to brainstorm the solution here

[patent acorn]

i think what i'd do is, decompose it into powers of primes

so 5, 7, 8, 9, we leave as they are

x = 3 mod 6 is the same as x = 1 mod 2 and x = 0 mod 3

then with mod 2 and mod 8, you just have to check that they're compatible (if it was x = 1 mod 2 and x = 6 mod 8 for instance then there's no solutions), and then you can just ignore the mod 2, because mod 8 is more information

same with mod 3 and mod 9

and then it's just 5, 7, 8, 9, and those are all coprime

[merry cradle]

I found a way to do it

but thanks

[sacred junco]

@merry cradle Love fluttershy pfp

[raven dagger]

i was talking about for primitive roots g and h, $\text{ind}_g(x) \equiv \frac{\text{ind}_h(x)}{\text{ind}_h(g)} \pmod{\varphi(n)}$

[sterile pumice]

silverwildflower8

[raven dagger]

managed to figure it out though

[weary rune]

the case where $\gcd(a,2^{15}-2^3)=1$ is of course straightforward, but how do we proceed when that's not the case?

[sterile pumice]

elrichardo1337

[weary rune]

oh maybe it's like

the divisibility automatically holds for those primes that it has in common with $2^{15}-2^3?$

[sterile pumice]

elrichardo1337

[primal pewter]

@weary rune basically they want you to prove that each of 5,7,8,9,13 divides a^15-a^3

since these numbers are pairwise coprime, it follows that a^15-a^3 is divisible by their product

[weary rune]

yea i figured it out on my own, thanks tho

is there a way to write a solution that's not quite as longwinded as the one here?

[weary rune]

more worryingly the reasoning for the "s odd" case seems to be entirely incorrect

what about the cases where s is not 1 or 3 less than p-1?

[spare frigate]

@weary rune I did a similar problem and here was my solution:

so basically for the p=1 mod 4 case

s is odd because a power of a primitive root evaluates to -1 when the power is (p-1)/2

[weary rune]

oh aight

[spare frigate]

i’m reading ur proof rn, which part is this?

for the 3 mod 4 or 1 mod 4?

[weary rune]

8a

this is from some solutions manual i found online

[spare frigate]

ohhh i see, sry abt my mix up

yeah, 8a seems a little wordy to me

8b looks solid

[azure fox]

whoever dms me i will give them elementary math paper for them to solve

[still flare]

What an enticing proposition!!!!

[surreal tangle]

This offer is so tough to accept!!!!

[knotty nacelle]

Hi

Can someone teach me how to divide decimals

[weary rune]

wrong channel

[still flare]

You may find better luck in #prealg-and-algebra but I fear even then you will struggle to find help.

[fleet bone]

lmao

[keen pagoda]

hey uh, did you mean q = 15 or q-1 = 15?

it's the entire set

all the elements

sorry I suddenly decided to try this problem out again and I think I know what I'm supposed to do but forgot a lot of stuff

so like since the cyclic group of order p-1 has order p-1 which is the same as summing phi(d1) + ... + phi(dk), and in this supposed set when we count we're going <= phi(d1) + ... + phi(dk) (because supposedly some are being 0), but the sum has to be p-1 anyways so they must have both the same amount of orders for each divisor?

[primal pewter]

as far as I remember we replaced q-1 by q, so that q is supposed to mean "q-1"

the number of elements in a finite field is always a power of a prime

[keen pagoda]

ok but I solved it yeeey

ty for your tips they made no sense to me 5 months ago but now that seems so obvious lol

yours' and toposphere's

[weary rune]

"E2: Given an integer a, prove that the correspnding element [a] in Z/nZ is invertible if and only if gcd(a,n) = 1."

is [a] just the residue mod n?

in which case it's a very straightforward proof using division algorithm and gcd?

[jovial herald]

Well, if $\gcd(a,n)=1$ then there exists $x,y\in\mathbb{Z}$ such that the linear combination $ax+bn=1$ is minimal.

[sterile pumice]

bondalton

[jovial herald]

How could you prove that $\overline{a}\cdot\overline{x}=\overline{1}$?

[sterile pumice]

bondalton

[weary rune]

$ax-1=bn,$ so $ax\equiv 1\pmod{n},$ seems pretty straightforward

[sterile pumice]

elrichardo1337

[weary rune]

if we want to minimize a, then we turn to the division algorithm

pull out as many ns as we can

and then it should work

[sacred junco]

so does "reduces to" mean that we're subtracting the equations? how did that happen? I've no clue where that equation came from and the next absolute value stuff also. why is that equal to 5 if a_{i+1} is not equal to a_{i}?

<@&286206848099549185>

I've understood everything else including depending on whether i is even or odd

[sacred junco]

srry for the ping guys im not sure if im allowed to use this in this channel

[primal pewter]

"This equality simplifies to either A or B, depending on whether i is even or odd" simply means that if i is even then you have A, and if i is odd you have B.

"reduce to" ≈ "lead to"

[sacred junco]

could you please explain the step before -- how did it lead to 2(a_{i+1} - a_{i})

I know this maybe trivial but I'm a beginner :(

[primal pewter]

just use this:
x = y (mod 10) => x-y = 0 (mod 10)

[sacred junco]

Could I get a hint for this problem?

[coral venture]

There is quite a lot to do in this problem

How far have you gotten?

[sacred junco]

I’m still trying to show that $\psi$ is multiplicative. I know there’s a way to solve it using CRT, but the textbook hasn’t introduced congruences yet, so I’d like to avoid using it

[sterile pumice]

eigenpuppet

[sacred junco]

My current approach is to find an expression for $\sum_{d|n} \psi(d)$, which would hopefully be multiplicative, then applying Mobius inversion

[sterile pumice]

eigenpuppet

[mint vault]

a. If $p, q, r$ are prime numbers and $p\neq q$, what is $gcd(p, q)$? What is the smallest positive integer of the form $px + qy$ where $x, y \in \mathbb{Z}$ ? What is the smallest positive integer of the form $rpx + rqy$? If $p\mid rq$, prove that $p \mid r$ and deduce that $p=r$.

b. Use part a to prove that it is not possible to find four distinct prime numbers $p, q, r, s$ such that $ps-qr=0$.

[sterile pumice]

duk

[mint vault]

I know gcd(p,q)=1, and thus the smallest positive integer is 1 from bezout, giving px+qy=1 , and i can get the RHS to be r(px+qy) and then just r, but im confused obout the LHS.

[patent acorn]

...the LHS of what

[mint vault]

if i have rpx+rqy

i dont know what to se t that equal to

just r?

[patent acorn]

why would you set it equal to anything...?

[mint vault]

im having a hard time convincing myself that r is the smallest positive integer

[patent acorn]

well r | r(px+qy)

[mint vault]

oh

thats what I do?

i can work from that

thats clever actually

thank you

one other quick clarification question

$\mathbb{Z}^{\times}_{12}$ is jus the set of integers coprime to 12?

[sterile pumice]

duk

[mint vault]

{1,5,7,11}?

beacuse its asking m to constuct a mulitplication table to see if i suggests that set is a group

and if it is {1,5,7,11} it is a group but if its {1,2,3,...,11} it is not a group

its jsut the notation confusing me

[patent acorn]

i would guess {1,5,7,11} but also probably they defined this notation at some point so if you can just find that that will tell you what it means here

[mint vault]

yeah my professor must have said it in class but i cant find it in my notes

im just going ot assume it is

beacuse ottherwise the problem is way more pointless

thanks

[weary rune]

for 3.2, is it sufficient to say $g^m\equiv\pm 1\pmod{p}$ but we cannot have $g^m\equiv 1\pmod{p}$ since that would contradict our order assumption?

[sterile pumice]

elrichardo1337

[tulip marlin]

I don't know why this holds.

[weary rune]

wow what a very specific and informative statement!!!!!!!!!!!!!!!!!!!

what about it doesn't make sense? why?

[primal pewter]

yes

[sacred junco]

Guys does there are any theorem like this:
For n consecutive real numbers,their product is divisible by 1.2.3....n

[still flare]

Real numbers? is 0.5 * 1.5 divisible by 2?

[sacred junco]

Oh shoot

Natural

Sorry

[still flare]

Anyway this is false

Wait, whoopsie daisy, my supposed counterexample was wrong

[sacred junco]

I tested it

And proved it

[still flare]

OK so...

[sacred junco]

Using mathematical induction

[still flare]

Right, this is just (n+k choose n) is an integer

So there you go. It's the binomial coefficient theorem I suppose

[sacred junco]

Thanks

Come back to the grind

Lol

[weary rune]

n! divides the product of n consecutive integers

this is just pigeonhole

[primal pewter]

is it?

[weary rune]

should be?

repeatedly apply div algorithm

oh wait

LMAO

[runic token]

[weary rune]

😭

[sacred junco]

Yeah at first I just don't know why product of 3 consecutive integers is divisible by 6 and I smh figured out and generalized it

[spice escarp]

Out of curiosity, what are the pre-requisites (if any) to learn about elementary number theory, if I'm just trying to self-learn?

[sacred junco]

If you are familiar with proof writing, you’ll be fine

[spice escarp]

Alright, nice

[fleet bone]

really when i started

i was 13 yo iirc

i knew freaking nothing outside school

like i did some non routine maths for own curisioty characterizing nth fibonacci number on my own and stuff which i didnt learn formally

[fleet bone]

just to clarify i only did for MO

so really ig that much is enough '

[wheat patio]

I'm doing a unit on Euler's theorem/Euler's Phi function, but I don't believe this part was gone over in class. Would anyone be able to help me get started on solving this?

[primal pewter]

hints: ||you want to calculate 27^162 mod 100||
||use Euler's theorem||

[wheat patio]

That mod 100 is exactly what I needed, thank you!

[wheat patio]

One more problem. I want to use induction here, but I don't know if I can. I think im supposed to use the properties of the phi function with primes, but i dont know where they'd fit either

Here's what I have so far

[primal pewter]

induction doesn't work
you can use the definition: phi(n) = the number of integers in the set {1,2,...,n} that are coprime to n
||try to make some pairs||

[narrow eagle]

we don't learn numbers like this in my elementary school 😞

[narrow eagle]

Multiply 27 by itself 161 times, take the last two digits and you have your answer.

[wheat patio]

I think I can see where you're going with this, but could you clarify a bit more on what I should try pairing based on?

[primal pewter]

For example, for n=14 we can make the following pairs: (1,13), (3,11), (5,9)
you can generalize this

[wheat patio]

Does it have to do with the second number in the pair being 14 - the first number?

[primal pewter]

yes

[wheat patio]

aight i think i have it now, thank you very much!

[wheat patio]

Does this proof look okay? It feels like it's missing something @primal pewter

[primal pewter]

you should also mention that k≠n-k

[wheat patio]

Isn't that already given since gcd(n,k) 1? Since if n-k=k, then n =2k

[primal pewter]

yes, it follows from gcd(n,k)=1, but it should be mentioned in the proof

[eternal pike]

https://cdn.discordapp.com/attachments/903430333888884736/1233115235146272768/image.png?ex=662beb8e&is=662a9a0e&hm=ca2ae47952fb27a7318101d9346f9fe445246a593bcd5d5ef9142c5a0e66c469&

does anyone know

[primal pewter]

@eternal pike 10000 = 2^4 * 5^4 and by CRT it is enough to prove that a^1000 = 1 (mod 2^4) and a^1000 = 1 (mod 5^4)
||you can use Euler's theorem for this||

[eternal pike]

right since a^euler(n)=1 mod n if gcd(a,n)=1

so euler(625)=500, HENCE A^500=1 mod 625, so (a^500)^2=1^2=1 mod 625

@primal pewter

[primal pewter]

@eternal pike yes, that's correct

[inner wolf]

chat

am I wrong with the comment

under the definition

like there's no such thing as a non-finite cyclic group no?

then it wouldn't be a cyclic group

also here ^n isn't to denote exponentiation

it's just repeated applications of the binary operation of the group

I'm just not sure if a non-finite cyclic group is a thing

yah but then would it be called a cyclic group?

there's no cycles

by definition a cycle would cause it to be finite is what I"m tryna say

but I don't know if non-finite cyclic groups is a thing

that's why I'm asking here

interesting

so the comment is indeed wrong

so is that all the definition of a cyclic group?

where the fuck is the cyclic in that

pretty misleading naming if you ask me

but oh well

[west glade]

well it still has a lot of similar properties. so why not call it cyclic aswell. you have to get used to suboptimal names in math

[shell minnow]

Sir are you saying T1/2/3/4/2.5 is not genius naming?

[river rapids]

hello guys

if i want to compare two functions that have different points

how do i do it?

would it be to check the integral?

and give it some volume?

[west glade]

well what should that comparison do

[river rapids]

check the difference between the real solution and the approximated solution

but it doesnt make any sense because i have a singularity in my function and i dont know if the integral is finite or not

[fleet bone]

this doesnt fit in #elementary-number-theory prolly

[keen pagoda]

in Z[x], if p(x) is an irreducible polynomial and p(x) | f(x)g(x), does that imply p(x)|f(x) or p(x)|g(x)?

[still flare]

Z[x] is a UFD so indeed irreducibles are prime.

[quiet epoch]

Find all numbers $n \in \mathbb{N}$, such that $\varphi(n)$ is prime.

For this problem I found $n = 3$ as a solution, when assuming that n must be a prime too. With that and a little trying around I found out, that this also works for $n = 4$ and $n = 6$. However.. I have to find a general form for n or proof that, there's no other $n$ that satisfies this equation. Could someone help me out with that or provide a little hint to me? 😅

[sterile pumice]

Edlingem

[west glade]

have you calculated a few more values of phi(n) ?

[open mist]

the case n prime is solved as unless n = 3, n-1 is even and therefore not prime
Otherwise you may want to remember that phi is multiplicative...

then there's just the case n = p^k left to handle

[quiet epoch]

But there could always be another p, k such that phi(p^k) is also prime isn't it?

[open mist]

I claim you shoudn't need a hint for that one

it's not hard to work out from the explicit formula for phi

[quiet epoch]

You mean phi(p^k) = (p - 1)p^(k - 1) ?

[open mist]

which is clearly composite except in easily found cases

[river rapids]

thought this was numerical analysis sorry

[keen pagoda]

I thought like, that that one theorem only applied if the thing has a multiplicative inverse for non-0 values

also what's ufd

soooooo

[still flare]

Dunno what you're referring to. The acronym "UFD" stands for "Unique Factorisation Domain."

[keen pagoda]

yeah that

I forgot what a domain is

I meant that I assumed that being a unique factorisation domain needed that multiplication had an inverse (excluding 0)

which isn't true in Z

[still flare]

No

[keen pagoda]

is this proof of that theorem that if p/q (in reduced form) is a root of an integer polynomial f(x), then the leading coefficient is divisible by q and the lonely coefficient by p correct?
f(x) = (x-p/q)g(x) (over Q[x])
qf(x) = (qx - p)g(x)
multiplying by a convenient integer d
dqf(x) = (qx - p)z(x) (with z(x) in Z[x])
so qx-p divides dqf(x), so it divides one of the terms, and obviously it's f(x), so
f(x) = (qx-p)(ln-1x^n-1 + ... + l0)
with lk an integer
so when you distribute it, the leading term is qln-1x^n and the lonely term is -pl0, with proves the theorem

also what's the name given for the coefficient in x^0? I call it lonely but I forgot if it has a name

standard name

[still flare]

The constant term

[keen pagoda]

ty

[still flare]

looks like a fine proof on a quick read

[agile grotto]

finding remainder of quotient 3^302 divided by 28 without calculator.
Can someone tell me if there is a simple approach to this, or whether it comes down to using several arithmetic tricks?

(please don't tell solution though, I just would like to know if I should search an alternative to doing lots of arithmetic)

[west glade]

the key observation is that if you have two numbers x and y and you want the remainder of xy, then instead you can take the remainders of x and y, multiply those together and then take remainder again. which lets you have much smaller numbers

the general topic is called modular arithmetic

[agile grotto]

yeah this is what i mean by "lots of arithmetic"

[west glade]

try calculating just the first few

[agile grotto]

if i want to compute it it involves several calculations, unless I'm missing some more insights

[west glade]

you'll notice something

otherwise you can use eulers theorem if you know that

[agile grotto]

I think I did yesterday

but I'll retry

[open mist]

It can't be more than phi(28) = 12 multiplications anyways

[west glade]

3^3=27=-1 btw

[open mist]

That insight makes it 2

[agile grotto]

please mind I didn't want too much of a solution

thanks for the help so far

[stone root]

Guys i need help im taking elementary number theory this semester and i could use some help for a problem as follows (p,p+2) is a primetwin with p >=5 then p ≡5mod6 i assume that this quite a easy problem but i have no idea how to approach it even for example in algebra or topology u define structures and then proof certain statements relations between objects within the realm of those structures and given lemmata so if somebody gives u a set and you’re supposed to proof its a group u check the axioms but with number theory its so different so my question by extend would be how do you approach number theory statement. Because to me those don’t like proper mathematical excersices more than math Olympiad problems which i never did.

[coral venture]

What happens to p+2 if p is 1 mod 6?

[runic token]

given that 2 \equiv 2 mod 6 what do u think

[indigo echo]

I spent the last 4 years working a number theory problem with no formal training on number theory. The closest I've been is linear and discrete, and that was a long time ago. I've forgotten most of the math I know.

Anyway, $$e^{\sum_{x_{1}=2}^{x}\ln\left(\left|-\frac{x_{1}}{2\pi}\left(\arcsin\left(\sin\left(\frac{\pi\left(x-\frac{x_{1}}{2}+1\right)}{x_{1}}\right)\right)-\arcsin\left(\sin\left(\frac{\pi\left(x-\frac{x_{1}}{2}-1\right)}{x_{1}}\right)\right)\right)-\frac{\left|x-1\right|+\left|x-x_{1}+1\right|-\left|x-x_{1}-1\right|-\left|x+1\right|}{2}\right|\right)}$$

I posted this in math discussions, but I don't know if that's the right place.

I'm not looking for help so much as understanding.

[sterile pumice]

Jarhyn

[indigo echo]

Anyway, it's a prime indicator function. You can actually drop the e and the exponentiation and find the max of that and the line at 0, and it still works.

I don't know enough about prime indicator functions or what the challenges are or even what challenges people are trying to overcome, and (a little bit) whether I'm wasting my time.

[blissful shell]

g

[weary rune]

what is the general procedure for these? does it involve using euler's theorem and seeing if things line up?

[wooden glen]

I don't think you should be looking for a "general procedure" there.

[weary rune]

hmm

[surreal tangle]

You should find a solution mod 5

[weary rune]

in both cases i see that x^20=1 mod 25 by euler

do the solutions mod 5 cover all solutions mod 25 necessarily?

[wooden glen]

Every solution mod 25 is also a solution mod 5, at least.

So solving mod 5 would let you eliminate a lot of possibilities mod 25.

[weary rune]

would i need to manually check the remaining ones

[wooden glen]

Don't think in terms of "need to". Think in terms of "find something that works", and don't (at first) worry about whether that's the only thing that could possibly work.

[weary rune]

looking at mod 5

it looks like the only solution (for part a) is 1 mod 5?

[wooden glen]

That could get you some of the way for x^4=1 -- it tells you that every fifth power (of a unit!) will work.

[torn escarp]

hensel's lemma will guarantee that the lift is unique if you satisfy the conditions

[weary rune]

we didn't cover that in class 😭

[torn escarp]

bummer!

[surreal tangle]

I was just going to say: https://youtu.be/nrH2vs04TyQ

[weary rune]

the teacher was literally just reciting this shitass textbook verbatim

hmm i think i have smth for a

considering the congruence mod 5, we have x^3=1 mod 5 and x^4=1 mod 5

therefore, letting k=ord_5(x), k divides 3 and k divides 4

but that forces k to be 1, and thus x to be 1

taking this back to mod 25, it's easy to see that 6, 11, 16, 21 don't work, while 1 does

so answer 1

[torn escarp]

we can kinda reinvent part of hensel without doing the full thing

like once you solve for some a that makes a^3=1 mod 5, you can then substitute in x=a+5b and see what b can be

(a+5b)^3=1 mod 25
a^3+3a*5b = 1 mod 25
since you know a^3-1 = 0 mod 5, you can factor out a 5
5 * ( (a^3-1)/5 + 3ab) = 0 mod 25
since you have two things that multiply to make something 0 mod 25, and one of them is 5, then must be
(a^3-1)/5 + 3ab = 0 mod 5

that's a linear equation for b that's uniquely determined, so there can only be 1

[weary rune]

one possible b?

[wooden glen]

For each a that works.

[weary rune]

and we found only one a from above

so that would lead to exactly 1 sol?

[wooden glen]

Yes, agreeing with what you found by trial and error here.

[weary rune]

aight aight

I will need to sleep on this lmao, tired and my exam is day after tmrw

thanks for the help

[torn escarp]

goodnight goodluck

[patent acorn]

i haven't looked at the formula in enough detail to say for sure, but based on just what it looks like... yeah i suspect this probably isn't very useful

the concept of a "formula" is arbitrary and ill-defined anyway

the interesting thing about any new discovery about prime numbers will be that it actually expresses a pattern that wasn't previously known to exist, not "is it in words or is it a pile of symbols"

and my guess looking at that is that once you simplify all the $\arcsin(\sin(...))$ and stuff out, it comes out to ``a number is prime iff its only divisors are $1$ and itself'', which is not a new discovery

[sterile pumice]

bee [it/its]

[patent acorn]

if there is some new insight about the prime numbers here then the first step would be to convert it out of this ridiculous encoding to a statement in words

if the encoding was in itself somehow useful, then it would probably be more because of the general facts of what you can use tricks like absolute value, arcsin(sin(...)), and summation, to represent, with the special case of prime numbers being just one example of a far more general result

[indigo echo]

More, it goes to discussing what I've been led to believe is an important result: prime indication at sum 0-sqrt(x) ln(f(x))

I've not done.much with it because I got it to that point just this weekend and have a day job and am very lazy after work.

That was ultimately my goal: prime indicator with a single sum operation through sqrt x

Thank you for your response BTW

[indigo echo]

I'm led to understand that things in the form $$\sum_{x_{1}=0}^{x}\ln\left(\left|J\left(x_{2},x_{1}\right)\right|\right)$$ are "important"

[sterile pumice]

Jarhyn

[indigo echo]

meh, bad pasting is bad...

[weary rune]

a is trivial by Lagrange but not sure how to approach b

by Fermat I see that a^p=ar=a mod p but now sure what to do with that

[weary rune]

anything?

i have a “fakesolve” by considering when r=1 but obviously that doesn’t work in the general case

[open mist]

If a is invertible, that means r = 1

[weary rune]

ah aight

so i could argue the only possible values of r are 0,1?

since if a is not invertible then that means a=0 mod p, r=0

[weary rune]

i am trying raising to p power to be able to use Euler

and then the order of r mod p^2 is 1 or p

is this a correct start ?

[indigo echo]

The really big question I have is if O sqrt(x) ln(n) as an operational cost basis for a prime indicator function is a noteworthy accomplishment.

It doesn't matter if people understand it yet. I still have to write the paper, if it is. Technically, I need to get help writing the paper from someone else.

[patent acorn]

...what are x and n here?

ok if i'm guessing correctly what that means... that's the exact same complexity as trial division, "check if each number up to sqrt(n) is a factor of n", which is an algorithm that's been known about for at least 800 years and is also pretty much the slowest way to check if a number is prime

[weary rune]

still walled on this 🫠

haven't been able to progress at all hooray

[torn escarp]

I'd reduce that mod p and use fermat's little theorem to show r=1 or 0 mod p

[weary rune]

just consider the congruence mod p at first?

[torn escarp]

yeah

[weary rune]

that seems pretty easy, just not sure how to "boost" it to mod p^2 in general

(our prof didn't go over this well at all)

[torn escarp]

you can think of it as determining the digits of the number in base p

so when you solve it mod p, you're getting the first digit, then mod p^2 you can use that to help get the second digit since it's already determined

[weary rune]

computationally what does that look like

are we claiming that the original congruence is unsolvable if r is not 0 or 1 or am i barking up the wrong tree

[torn escarp]

yeah, we'd show that first

x=a+bp is the number in base p, with a,b digits as usual from 0, 1, 2, ..., p-1

[weary rune]

is that the general form of the solution?

[torn escarp]

yeah, in general a base p number will be like a+bp+cp^2+dp^3+...

but because we're looking at it at most mod p^2, the higher digits are thrown in the trash

see what I mean?

[weary rune]

oh icic

oh so

do we fix that "units digit" and do stuff

[torn escarp]

that's second

first you throw away the "p's place digit" by reducing the equation from mod p^2 to mod p to solve for the "units digit"

then once you have it, it is fixed and you can go back up to mod p^2

[weary rune]

hmm ok

so when it's mod p, we only get a solution if r=0 or r=1

does that hold for mod p^2 as well or is this where the "digits" stuff comes in

im guessing not

but how to show?

[torn escarp]

well instead of thinking if it holds or not, you can think of it as determining the units digit of r

r=ps or r=1+ps are the only options next would be a way to think of it

[weary rune]

ohhhh

do we then check each or

[torn escarp]

we might have to, I guess let's be more concrete about it

[weary rune]

yes please lmao 😭

[torn escarp]

$$x^{p-1}=r \mod p$$
Now we're saying $$x=a+bp$$ so plug that in and we get,
$$(a+bp)^{p-1}=r \mod p$$
since $$p=0\mod p$$ the $$bp$$ term dies and we're left with just
$$a^{p-1}=r \mod p$$

Now if $a=0$ we have $r=0 \mod p$, and you use Fermat's little theorem for when $a \ne 0$ to see that it must make $r=1 \mod p$.

[sterile pumice]

Merosity

[weary rune]

oh ok we use that form from the outset

[torn escarp]

yeah, similarly we could have said r=s+pt let's say, and now we determined how a affects s

let's just split it into the two cases, a=0 mod p or a !=0 mod p which makes r=0+pt and r=1+pt respectively, and we have to solve for b and t now

so I can do one case and then we can try to do the next case together

[weary rune]

aight

[torn escarp]

Actually I'll let you help a bit, let's do the case: $a \ne 0 \mod p$ and let's do the same thing but mod $p^2$.

$$(a+bp)^{p-1}=1+tp \mod p^2$$
Expand out the binomial on the left there

[sterile pumice]

Merosity

[weary rune]

aight

all terms besides the first two cancel leaving us with

$a^{p-1}+a^{p-2}bp(p-1)\equiv 1+tp\pmod{p^2}$

[sterile pumice]

elrichardo1337

[weary rune]

even better, we can further cancel to get

$a^{p-1}-a^{p-2}bp\equiv 1+tp\pmod{p^2}$

[sterile pumice]

elrichardo1337

[torn escarp]

nice

[weary rune]

and now do we rearrange?

[torn escarp]

yeah

how do you want to rearrange

[weary rune]

$a^{p-1}-1\equiv p(a^{p-2}+t)\pmod{p^2}$

[sterile pumice]

elrichardo1337

[weary rune]

to get all the p terms onto one side?

[torn escarp]

I think factoring the p out is good, and I like to have them all on one side personally

I don't think it really matters but might make the reasoning clearer

a^{p-1} -1 is divisible by p, since that's really the original result we worked out showing that's 0 mod p earlier

[weary rune]

oh huh

[torn escarp]

a^{p-1} = r mod p I guess is what it really looked like but same thing if that's unclear

[weary rune]

for this case r=1+pt?

[torn escarp]

yes exactly we're just doing the r=1 mod p case first

[weary rune]

ok

[torn escarp]

and we said a !=0 mod p for now yeah

ok cool so

the way I think of it, working with stuff mod p^2 is harder because you have nonzero things that multiply together to make 0. But mod p, there's nothing that's nonzero that multiplies to make 0 mod p

it would be nice if we could turn this into a mod p problem instead of a mod p^2 problem

and we can

[weary rune]

do we divide out p from both sides + the modulus now

[torn escarp]

$$p(\tfrac{a^{p-1}-1}{p} - a^{p-2}-t) = 0 \mod p^2$$

[sterile pumice]

Merosity

[torn escarp]

you can't really "divide the modulus out" but sort of

the fact that p*x=0 mod p^2 means x=0 mod p

maybe I should use a different letter than x here, not trying to confuse with the previous x

[weary rune]

that stuff inside the parentheses?

is 0 mod p

[torn escarp]

yeah exactly

px=0 mod p^2 means px is divisible by p^2

[weary rune]

yea

[torn escarp]

we already know p takes up one of those so yeah

what's left must be divisible by p still, ok cool

[torn escarp]

oh you left out b up here and I copied your mistake

[weary rune]

oop lmao

[torn escarp]

so work it out to that point of what we have and let's see what we can do

[weary rune]

$p\left(\frac{a^{p-1}-1}{p}-ba^{p-2}-t\right)\equiv 0\pmod{p^2}$

[sterile pumice]

elrichardo1337

[weary rune]

so $\dfrac{a^{p-1}-1}{p}-ba^{p-2}-t\equiv 0\pmod{p}$

[sterile pumice]

elrichardo1337

[weary rune]

how do we rearrange from here

do we case on b or smth?

[torn escarp]

well the r from the problem was fixed and we can't change it

so there's really only one free variable here, can you solve for it?

[weary rune]

is it b?

a we have already made assumptions about its value, t is fixed from r

[torn escarp]

yup

[weary rune]

so multiplying by a gives us

$b\equiv \frac{a^p-a}{p}-at\pmod{p}$

[sterile pumice]

elrichardo1337

[weary rune]

and further,

$b\equiv -at\pmod{p}$

[sterile pumice]

elrichardo1337

[weary rune]

since the fraction vanishes by fermat?

[torn escarp]

nope fraction doesn't vanish because it's divided by p

[weary rune]

ah rip

[torn escarp]

a^p - a = 0 mod p is what lets us divide it by p, so we already "vanished" that part of it if that makes sense

[weary rune]

yea

[torn escarp]

cool, so hey we're done

b is uniquely determined at this point and we just solved for it no problems

[weary rune]

is that all we need?

oh huh

[torn escarp]

let's wind back to the start

[weary rune]

one b for each of the p-1 choices of t?

[torn escarp]

p-1 choices of a

t is not something we choos

r=s+pt was forced on us from the start

[weary rune]

oh

[torn escarp]

we still have the case a=0, s=0 to work out though

should be same kind of game

[weary rune]

that sounds like it's gonna be a bit easier lmao

ok time to try it

[torn escarp]

and probably we could work out the argument in general

without ever really specifying anything but I guss we'll find out, let's just do it yeah

you want to try to start it out and see how far you get

[weary rune]

sure

[torn escarp]

I just made ramen earlier so about to start eating it, so take your time lol

[weary rune]

lmao aight

in that case, it looks like the entire LHS cancels?

bc a is 0 mod p

well

if p=2, the a term is left behind

p>2, everything vanishes mod p^2

$0\equiv pt\pmod{p^2}$

[sterile pumice]

elrichardo1337

[weary rune]

how many solutions does this generate?

for p=2, a-2t=2b mod 4

but 2 is not invertible mod 4

a/2-t=b mod 2?

and for p>2, t=0 mod p

[weary rune]

does this imply no solutions or

[torn escarp]

well pt=0 mod p^2 means t=0 mod p so it sorta forces what's possible there for r

since b isn't anywhere to be found, it can be anything

[weary rune]

so p-1 sols as well for this one

and i take it it's no sols for any other values of r that don't have s=0 or s=1?

[torn escarp]

actually p, not p-1

but it also means r=0+0p

[weary rune]

hmm

the problem statement claims that either there are 0 sols or p-1 sols

idk whats going on there

[torn escarp]

well we just worked it out

[weary rune]

yea

when do we have the 0 case

[torn escarp]

the 0 case means x=0 mod p and r=0 mod p^2

[weary rune]

oh i meant "0" as in "no solutions"

[torn escarp]

ah, that's here when t !=0 mod p

keep r in mind as being fixed and we sort of have to answer to it

[weary rune]

oh aight

the problem statement also said "r coprime to p^2" so i think that resolves the discrepancy i was having earlier

the case with p solutions seems to be out of scope for this problem lol

aight thanks for the help!

my exam is tmrw i hope i don't bomb 😭

[torn escarp]

ah yeah you got it, yw

gl

[weary rune]

thanq

[indigo echo]

N is bigO(n). X is the number. See chapter this:
https://nap.nationalacademies.org/read/10532/chapter/18#245

[patent acorn]

"n is O(n)" does not clarify it at all, because i still have the question of... what does the "n" in that "O(n)" mean

but ok yeah it looks like i guessed mostly correctly - this is the same complexity as trial division, and in fact i think it is trial division, so it's not really new at all

the fastest known unconditional deterministic primality test takes O((log x)^6) time, and if you allow probabilistic tests (tests that work most of the time) or tests that depend on unproven conjectures (so they might always work but we don't actually know) then there are even faster methods, by comparison O(sqrt x) is so slow it's only useful if either the numbers are really small or you just don't care at all about how fast it is

[agile grotto]

in order to prove that a^2 - b^2 where a,b are integers can represent any odd integer, what approach would you choose?

[coral venture]

I would explicitly construct a representation

[agile grotto]

so doing transformations to a^2 - b^2 until it is in a form 2n + 1 or similar?

[coral venture]

No

Well kinda

But you are free to choose a and b however you like and you should use that

[agile grotto]

it works though

add a case distinction in and it appears the prove leads somewhere

oh wait maybe i made a mistake

think it worked

no case distinction. just what you said: choosing however i like

thanks

[half yacht]

is it a good idea to use this thing instead of the Extended Euclidean Algorithm to solve for modular inverses, in the context of problem sets?

[distant sandal]

i dont understand the contrapositive part

i would view 'with' to be the same as 'and'

and i see contrapositive as

a not divide c -> a not divide (bc) or gcd(a,b) not equal to 1

[primal pewter]

you are right; it is not quite the contrapositive

but it's true nonetheless

[keen pagoda]

how do we know that Z[x] is an UFD?

cus the proof I know that K[x] is an UFD assumes K is a field

is this related to the theorem that f(x) is irreducible in Z[x] iff it's irreducible in Q[x]?

[runic token]

http://homepage.math.uiowa.edu/~goodman/22m121.dir/2005/section6.6.pdf
here's a quick reference

in particular: if R is a ufd, R[x] is a ufd

[sturdy hemlock]

so i came across an interesting concept from a comment i saw on reddit, and im hoping someone can point me towards more info. Essentially the idea was to assign a group of people 1 prime number each, in order to track a relationship that a person would have to a potential "thing". So imagine if we had an ordered pair set of people in the form of (person, prime) and an ordered set of "things" in the form of (thing, composite) where the composite number is a product of all the primes of each person who has a relationship to whatever that thing is. This way you can quickly find if a thing has a relationship to a person by checking if the person's prime evenly divides the composite number. So my questions are:

1. Is there a name for this concept?
2. Is there an alternative so that the composite number doesn't get stupidly large if we have more than a handful of people with a relationship to a thing?
   p.s. im aware that this is the fundamental theorem of arithmetic that's not what im looking for :p just to be clear

[fleet bone]

Easiest way is to just kill it using primtive root

Let $g$ be a primitve root working p^2

[sterile pumice]

lucid
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[fleet bone]

so $g^{(p-1)t}=r(mod p^2)$

[sterile pumice]

lucid

[fleet bone]

say $r \equiv g^k$

[sterile pumice]

lucid

[fleet bone]

so we basically want no of solutions of $(p-1)t \equiv k(mod p(p-1))$

[sterile pumice]

lucid

[fleet bone]

Finishing it up from here is easy

infact can be generalized to p^t

[torn escarp]

an alternative is to create just a list of names of the people and throw out the primes altogether if you really want to do it quickly 😛

[rapid plover]

Does anyone know of any quick intros to/references on the legendre symbol? I just need to get somewhat up to speed to use it for exercises in my algebra text

pls ping : )

[wooden glen]

Most likely "the entire chapter on quadratic reciprocity in your algebra text".

[rapid plover]

hm. the algebra text doesn't contain anything on quadratic reciprocity and has introduced the legendre symbol in an exercise which I had trouble understanding

[wooden glen]

Huh, I didn't think it was used for anything other than quadratic reciprocity.

In that case https://en.wikipedia.org/wiki/Quadratic_reciprocity might be a start -- or just ask here about whatever confuses you.

[rapid plover]

That might be true, and the exercises are probably "quadratic reciprocity" results. It's just that it feels very unmotivated and as if the author wanted to stick on some applications to the ring-theoretic results that we've been considering

I'll take a look at the wiki, cheers

[fleet bone]

ivan niven

[rapid plover]

thanks

[runic token]

the bit on it in ireland rosen is fine

[trim jungle]

why 13(17)

[torn escarp]

they give you the prime factorization so you can use the multiplicativity property of the euler phi function

[trim jungle]

,w phi(221)

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by xbz.24

[trim jungle]

is there a way with less machinery involved?

[torn escarp]

use the multiplicativity property of the euler phi function

[trim jungle]

if gcd(m, n) = 1, then φ(m) φ(n) = φ(mn).

what about it

,w phi(13)

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by xbz.24

[trim jungle]

,w phi(17)

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by xbz.24

[trim jungle]

I dont get it

[torn escarp]

do you know what phi(p) is when p is a prime number

[trim jungle]

is the same number

φ(p)=p-1.

what, why p-1

[sacred junco]

every number less than p is not divisible by it, and p’s only prime factor is itself.

[trim jungle]

what is the difference between coprime and reltively prime

[trim jungle]

got it

[sacred junco]

they’re the same thing

[trim jungle]

got it

sorry, im new to math

sorrry if stupid questionx

,w 12*16

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by xbz.24

[sacred junco]

no need to apologize

[torn escarp]

at a minimum, google for how to find an egyptian fraction representation - then try to do that. If you are not able to do it, then post what you've tried.

[trim jungle]

I googled but didnt understood

can you guys help?

,w egyptian fraction 20/13

[sterile pumice]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by xbz.24

[trim jungle]

help

[small hare]

Isn’t it just representing a fraction as a sum of fractions with numerator 1?

When in lowest terms

[wooden glen]

Yes, but the terms must be different.

So you can't just say 1/13+1/13+1/13+....+1/13.

Evidence of their purpose is pretty much nonexistent. My personal guess is that they initially thought it would lead to unique representations, and by the time they discovered counterexamples to that, tradition and inertia kept the system around.

[trim jungle]

is that egyptian fraction representation

[wooden glen]

Yes.

[trim jungle]

3 is a factor of 33

,, 5 \cdot 33^{7000321} \cdot 3^{7000321} \cdot 3

[sterile pumice]

milanesa de pollo

[trim jungle]

,, 15 \cdot 99^{7000321}

[sterile pumice]

milanesa de pollo

[wooden glen]

And 99 == -1 (mod 100)

[trim jungle]

?

can you explain that

I ddidnt got the lightbulb moment

[wooden glen]

"The two last digits" is another way to say the congruence class modulo 100.

[trim jungle]

?

why -1

[wooden glen]

Do you disagree that 99 == -1 (mod 100)?

[trim jungle]

no

im asking how did you

[trim jungle]

Is that CRT

?

[wooden glen]

What?

[trim jungle]

I need more hints

[torn escarp]

sounds like you need a book or course on the subject to give you more structure to learn these topics

[wooden glen]

Yeah, it sounds like you're not really conversant with modular arithmeticl, in which case you shouldn't be trying to solve "last n digits of such-and-such" problems.

[weary rune]

i've observed very similar behavior in a lot of other channels that they're active in

they're asking about stuff that it is apparent is above their level, without the foundational skills necessary

[cloud dew]

any recommendations for such books?

[torn escarp]

I think Silverman's A Friendly Introduction to Number Theory is a nice book, but might be too friendly depending on what you're going for as an intro

[cloud dew]

I see, I'll go though that and see, complete beginner here so it should be fine. Thank you!

[torn escarp]

cool enjoy

[trim jungle]

how do I use little fermat theorem to find all the residues of a^3 mod 7

and why since 7 is prime I dont need to check all the residues

Wtf

(a^3)^2 maybe?

if 7 does not divide a, what does that mean for the residues

[weary rune]

why don’t you try it out first

0^3,…,6^3 mod 7

what values do they take on?

and how can you explain why they take on the values they do take on using Fermat?

[wooden glen]

Since the exponent is already smaller than p-1, I don't think there's much to do for Fermat's little theorem in this particular task.

[primal pewter]

the exponent is (p-1)/2 though, so Fermat is helpful

[wooden glen]

Hmm, right.

[distant sandal]

I do understand the proof but I'm also contemplating what happens if you sub in n = 4 into n = d1 x d2

if n =4 then d1 x d2 - 1 = 3 so it wouldnt work

it makes sense now

[cobalt hornet]

x^2 ≡ 251 mod 779. how to prove that this has solutions? it is easy to show that x^2 ≡ 251 mod 19 and y^2 ≡ 251 mod 41 has solutions but how can i write down the prove in a good way

[primal pewter]

once you established that those congruences have solutions, choose "a" a solution for the first one and "b" a solution for the second one;
then consider the system
t ≡ a (mod 19)
t ≡ b (mod 41)

[cobalt hornet]

So x^2 ≡ 251 mod 19 ≡ 4 mod 19, then x ≡ 2 mod 19 implies x^2 ≡ 4 mod 19, similarly y ≡ 13 mod 41 implies y^2 ≡ 169 mod 41 ≡ 5 mod 41 ≡ 251 mod 41

[primal pewter]

yes, that works

just a remark: we don't necessarily need actual values for a and b

one can establish that they exist using Legendre's symbol

[cobalt hornet]

how would you write it formally regirous as a full answer?

[primal pewter]

so that's a good start; then consider the system that I mentioned and use CRT to establish that it has solutions

then generate a solution for x^2 = 251 (mod 779) based on t

[cobalt hornet]

what do you mean by generate. Since i have found such x and y then
z ≡ 2 (mod 19)
z ≡ 13 (mod 41)
than z has a unique solution modulo 779

[primal pewter]

I meant "find"

but in fact t is the solution

[cobalt hornet]

so i think thus z^2 ≡ 251 mod 779 has solutions direclty

[primal pewter]

yes

[cobalt hornet]

but im unsure of the formality writing way

i also did it in that way before

but have a bit trouble about how to write it down formally in a good way and reasoning

[primal pewter]

give it a try

I can help with the details

[cobalt hornet]

since x^2 ≡ 251 mod 19 ≡ 4 mod 19, then x ≡ 2 mod 19 implies x^2 ≡ 4 mod 19, similarly y ≡ 13 mod 41 implies y^2 ≡ 169 mod 41 ≡ 5 mod 41 ≡ 251 mod 41, there is a z in Z by CRT s.t.
z ≡ 2 (mod 19) (implies z^2 ≡ 251 (mod 19))
z ≡ 13 (mod 41) (implies z^2≡ 251 (mod 41))
thus this system has a unique solution for z^2 modulo 779. Since 251 is a solution, by uniqueness this implies z^2 = 251 mod 779 has a solution.

[primal pewter]

you should mention CRT when you introduce z

by CRT there is z such that...

I won't write "z ≡ 2 (mod 19) and z^2 ≡ 251 (mod 19)" because the second one is implied by the first one, so it's not like we have two conditions

such that "z=2 (mod 19) and z=13 (mod 41)"

and then mention that this implies z^2=251 (mod 19) and z^2=251 (mod 41)

[cobalt hornet]

here im a bit unsure of saying z^2 ≡ 251 mod 779 has a solution. I would rather say that by CRT z^2 has solution modulo 779

but there the information that z^2 ≡ 251 mod 779 is missing

[primal pewter]

we don't need unicity for this part, and in fact z is not unique modulo 779 (only z^2 is unique)

the point here is that CRT guarantees that the conditions z^2=251 (mod 19) and z^2=251 (mod 41) are equivalent to z^2=251 (mod 779)

[cobalt hornet]

why? i dont see it clearly from the definition.

"Let p, q be coprime. Then the system of equations
z ≡ a (mod p)
z ≡ b (mod q)
has a unique solution for z modulo pq."

[patent acorn]

so the system z^2 = 251 mod 19 and z^2 = 251 mod 41 has a unique solution for z^2 mod 779

namely z^2 = 251 mod 779

[primal pewter]

the system
x=a (mod p)
x=a (mod q)
has a unique solution mod pq, but "a" is a solution, so x=a (mod pq)

but we don't really need CRT for this argument: we have p | x-a and q | x-a, so pq | x-a

[patent acorn]

the other direction, that if x = a mod pq then x = a mod p and x = a mod q, just follows from the fact that if two numbers are equal mod pq they're equal mod p

[cobalt hornet]

oh i see now ur pont

[cobalt hornet]

yep that clears

[patent acorn]

yeah the point where crt matters is uniqueness

there isn't any other z^2 such that z^2 = 251 mod 19 and z^2 = 251 mod 41, that isn't equal to 251 mod 779, by crt

[cobalt hornet]

i see

[cobalt hornet]

is this now a rigorous proof?

[torn escarp]

here's a way to get an explicit construction, although it's not minimal it's clear when you reduce it mod 19 and mod 41 that it collapses back down since it either goes to 0 or 1 by flt:
z = 2*41^18 + 13*19^40

[shrewd gust]

Is 2 the right answer for a) and any hints for b)? In the proof of a) I noticed that the two solutions will be given by a ≡ 0 mod 2^12, a ≡ 1 mod 5^12 and a ≡ 1 mod 2^12, a ≡ 0 mod 5^12. Starting with the first, this means a = α2^12 so substituting in the second equation α2^12 ≡ 1 mod 5^12, so I guess I can write down the solution in terms of the inverse of 2^12 modulo 5^12, but that doesn't seem sufficient?

[primal pewter]

@shrewd gust the answer is indeed 2 for a)
you can use CRT to finish your proof

for b) you can work inductively by noticing that any solution for the equation modulo 10^(k+1) is also a solution for the equation modulo 10^k

[shrewd gust]

Oh what, so the solutions are just 376 and 90625 for all k >= 5?

[primal pewter]

no, because 376 mod 10^3 is not the same as 376 mod 10^5, for example

but the idea is to get information from smaller modulo

[shrewd gust]

Right, I see, but what is true is that the other solution for k=5 has to be congruent to 376 mod 10³, correct?

Because otherwise there would be 3 solutions for k=3

[primal pewter]

yes

the general strategy is to "lift" solutions from lower k

[shrewd gust]

Let me see if I can get that to work, thanks a lot!

[shrewd gust]

Mhm, I spent some time to calculate by hand that the second solution for k=4 is 9375, but I guess this isn't the winning strategy

Basically I solved (a+376)² ≡ a+376 mod 10^4 by hand to find a ≡ 9000 mod 10^4

Is there a more intelligent way to do the lift?

[primal pewter]

I'm thinking about finding some recurrences

according to WA these should be the solutions, so I guess there are going to be many calculations

[shrewd gust]

Yikes

[torn escarp]

One way is to start with 5 and keep squaring it until you get a to enough digits, then get the other one as 1-a since a^2-a=0 has two solutions a(1-a)=0 which is the other one, so you get both for free.

alternatively you can use the Newton recursion x_{i+1} = x_i - f(x_i)/f'(x_i) which actually doubles the number of digits with each iteration, so ceil(log_2(12)) = 4 steps that way

there's more to say about either method but I don't wanna swamp you - lmk if you have any questions or doubts

[long copper]

Can anyone help me with these problems I have zero clue how to do it

[wooden glen]

If you really have no clue, then cheat and do part (ii) first. You'll then notice a (very clear) pattern in which elements you can find inverses for, and you can then go back to (i) and pretend you knew all of the time that was the answer you had to justify ...

[long copper]

Thank you

[hollow dock]

is there a simpler method than euclidean algorithm?

oh

there isn't

nvm

[runic token]

there is: in a finite commutative ring every element is either a zero divisor or a unit.

since 16 = 2^4, and 8 = 2^3, any even class in the ring is a zero divisor. thus all the units are the odd class.

we only have to compute explicit units for prime numbers. then we just need to check 3, 5, 7, 11, 13. clearly 3 and 11 are paired, and 7 is paired with itself. then 5 and 13 must also be paired either with themselves or each other. 25 is not 1 mod 16 so they must be paired with each other, and it's easy to check 9 and 15 using (xy)^-1 = x^-1 y^-1

i personally consider this strictly easier than computing a shit ton of things with the euclidean algorithm.

hint for this:

in a finite commutative ring every element is either a zero divisor or a unit
||let R be a finite commutative ring (with unity, i guess) and let a\ in R ||
||consider f: R --> R, x \to ax||

note: in this case you can probably just look at it and do it but imo this is more generally useful

[wooden glen]

It looks like you're assuming the (canonical representative of the) inverse of a prime must itself be a prime? That happens to be the case here, but it's more by accident than by design because almost all of the odd numbers under 16 are prime anyway.
But for example the inverse of 3 modulo 256 is 171, which is not prime.

(I agree that such ad-hoc reasoning, or even exhaustive search, feels preferable to the the extended euclidean algorithm for moduli as small as 16, though).

[west glade]

also maybe worth noting that e.g. 3*7=5 mod 16, so knowing the inverse of 3 and 7 would be enough to find the inverse of 5. a number being prime in Z does not mean its prime in Z_n

[runic token]

fair!

[runic token]

oooh, def fair!

having said that, checking the normal primes works fine in cases like these too, i think

[wooden glen]

The real underlying point is that whether or not a number is prime in N has essentially no bearing on the properties of its image in Z/nZ. Indeed, every invertible element of Z/nZ will have both prime and composite representatives in N.

[paper trellis]

Eulers totient function is so cringe. What information can you even derive from an arbitrary natural number n just from knowing how many natural numbers less than n are coprime to n?

It feels like a random piece of trivia as opposed to an important function which is the engine behind some neat theorems that I want to understand.

[sacred junco]

The order of the group of units of Z/nZ is $\phi(n)$

[sterile pumice]

eigenpuppet

[sacred junco]

This lets you compute inverses in $U(Z/nZ)$

[sterile pumice]

eigenpuppet

[wooden glen]

And this again leads to Euler's theorem, which is an important tool for modular exponentiation.

[fleet bone]

HM well

last time i used euler tiotent

was becuase exponential

or it just serves as a helpfull notation

knowing a formula for which helps us do other things

[torn escarp]

I found all of these random number theory functions less cringe after I learned about the dirichlet convolution and how all these multiplicative functions form a group. Makes them a lot easier to play with

for instance, a proof that the multiplicative group of a finite field uses $\sum_{d|n}\varphi(d)=n$. That sum on its own at least isn't hard to derive knowing about some basic Dirichlet convolution stuff like the Mobius function.

[sterile pumice]

Merosity

[random smelt]

@primal pewter if it's not too much trouble would you mind checking my proof

[weary rune]

isn’t the Euler totient usually introduced directly in the context of euler’s theorem lol

[primal pewter]

There is an error when you express x^n - 1 in terms of S_n. It should be S_n = x(x^n - 1)/(x-1), so x^n - 1 = (x-1)/x * S_n.
However, this doesn't affect the calculation of the gcd, so the rest is correct.

Notice that the calculations can be done the same way directly on x^a - 1 and x^b - 1, without expressing them in terms of S_a and S_b.

[random smelt]

Thank you

I didn’t see the direct way but now I understand

[distant sandal]

suppose g = gcd(4, p - 1) = 2 then p - 1 = 2k where k is odd

im still confused by how k must be odd

(if k was even then g = 4)
i need more explanation for this one

[torn escarp]

you can plug that in directly, gcd(4, p-1) = gcd(4, 2k) if k is even then you could write it as k=2n and it would be gcd(4,4n)=4

[distant sandal]

Thanks 👍

[surreal escarp]

not sure it's related to the topic but is there a way to represent this in a simple expression? $$d_{m-1}\cdot a^{m-1}+d_{m-2}\cdot a^{m-2}+\cdots+d_{0}\cdot a^{0}$$

[sterile pumice]

horizon2.0

[surreal escarp]

at first i thought sum of geometric series but that doesnt work

[distant sandal]

sigma notation

[surreal escarp]

well yeah but i meant like some closed form, not sure sigma notaion will be of use to me, trying to prove that when moving from number base $a$ to number base $a^n$ you can take $n$ digits and convert them to a single digit in base $a^n$

[sterile pumice]

horizon2.0

[open mist]

summation by packets
Partition the summation space into different sets, then sum over the sums over each subset

[sterile pumice]

Fth

Fth

[magic drum]

anyone has any ideas for this?

this is special case of ramanujan’s theta function but im not sure how i’m suppose to manipulate the series to get to RHS

[stone root]

Im stuck at this Problem in number theory if 6m+1, 12m+1, 18m+1 are prime there Product is a Carmichael number iam supposed to proof that but don’t know how can somebody help me out.

[weary rune]

!status

[rotund gust]

What step are you on?
1. I don't know where to begin.
2. I have begun but got stuck midway.
3. I got an answer but I was told that it's wrong.
4. I got an answer and would like my work checked.
5. I have a question about someone else's work/solution.
6. I have completed the problem and don't need help anymore. Thank you.
7. None of the above

[torn escarp]

<@&268886789983436800>

[primal igloo]

Idk, but maybe you can shift n such that the sum is even about 0 and reduce that to a sum from 0 to infinity?

But what you have so far doesn’t look right

[wild spruce]

(Theorem.) Every integer $n \geq 2$ is either a prime or a product of primes.

[sterile pumice]

James

[wild spruce]

Since m is the least criminal, both a and b are "honest".

how did they deduce that?

or more clearly, how did they deduce that a and b are honest from the fact that m is the least criminal?

[torn escarp]

weird, they say it's not a "product of primes" but then say since it' snot prime, it's composite. I'm not really aware of a difference between "composite" and "product of primes"

[wild spruce]

oh right

gotcha

[wild spruce]

does that make the proof not valid in some way?

[torn escarp]

I'm assuming they define it in the context of the preceding 3 pages I've missed there to make the distinction

[wild spruce]

or is it just clever word-play?

hmm

[torn escarp]

clever? debatable

specifically this bit here looks like a contradiction to me to deduce, because it can't be composite since they specify it is not a product of primes

so any reasoning after that where they factor it as a composite makes no sense to me

[wild spruce]

so they try to make a distinction between "product of primes" and "composite numbers", where there isn't any?

[torn escarp]

but since this is page 4 of chapter 1, I'm guessing they like introduced these terms really quickly and this is like some kind of silly distinction they made to get started

[torn escarp]

I don't know without reading

or well, I won't read but you can reread and tell us 😛

[surreal tangle]

they claim that m must be composite(aka a product of primes), but just before that they say m is neither prime nor a product of primes(aka composite)

[wild spruce]

strange

Rotman is considered good for Algebra

[surreal tangle]

Okay, this definition makes sense with the proof you sent. Usually composite numbers are defined as a product of primes, but here it is not so. The definition only tells us composite numbers are not primes. It is our job to show that not primes must be a product of primes

[torn escarp]

so 1 and -1 are composite

[wild spruce]

hmm

[wild spruce]

oh okay

[surreal tangle]

I suppose the motives of the author(s) was to make the most minimalist(clean?) definitions possible, and deduce as much as possible. This strategy seems to have backfired.

[torn escarp]

tbh it's not even clear that 1 and -1 are not prime from their definition either haha

[torn escarp]

no I take that back, they do specify n >= 2 to be prime

[wild spruce]

[wild spruce]

what about this tho?

I am not still not able to clearly see this

[surreal tangle]

If m is the least criminal, all the other numbers smaller than m must be honest

[wild spruce]

oh shoot I think Eliza told me this

I have a goldfish memory :(

[surreal tangle]

Its like saying 3 is the least number greater than or equal to 3, so every number smaller than 3 must be smaller than 3

Haha happens, especially when you are in a mess of definitions like we are here. It is easy to lose track.

[wild spruce]

This book came in highly recommended

I resonate with the writing so far

it has a certain rhythm to it

I also skimmed some parts about permutation groups

[patent moss]

how do i find a solution to a linear diophantine equation ax+by=c?

[torn escarp]

extended euclidean algorithm

[slim parrot]

Something obvious, but I just wanted to confirm; here, we say the greatest common divisor of 2 integers can never be greater than max( |a|, |b|) because of the case where one of the integers is zero, right? Because if both of them are non-zero, the condition would reduce to gcd never greater than min(|a|,|b|)

[patent acorn]

it says

If a and b are not both 0
so no i don't think that's what's going on

i think you're right that the bound min(|a|, |b|) is true, it's just not what they decided to use

which is fair, there isn't actually any benefit in this situation to using a tighter bound, we just need that one exists at all

[slim parrot]

no, one of them can be zero, right? Just that both a and b should not be zero is what they mean ig

[patent acorn]

...oh right yeah that is what it says, i read it as "both not 0" lol

ok so yeah you're right

[slim parrot]

Ok, Thanks

[spark saddle]

How do I solve the modular equation

x^(12) ≡ 4 (mod 17) if 3 is a prime root of modulo 17?

[open mist]

Find the power of 3 that works
3 9 10 13 5 15 11 16 14 8 7 4 and then 12 2 6 1
So 4 = 3^12
How kind of them, you can skip step 2 here

[sacred junco]

hi weird question but

if a ≡ 2 (mod 3), b ≡2 (mod 3) does a/b ≡ 1 (mod 3)

btw a ≡ 0 (mod b)

[neat harness]

division doesn't exactly work the same way in modular arithmetic, while Z3 is a field and you can talk about 1/b, this won't hold true for every Zn. Instead you can think about 1/b as the multiplicative inverse of b, b^-1. With that in mind notice that 2^2 = 1 mod 3 so 2 is its own inverse, or rather b^-1 = 2 mod 3. Thus "a/b" = ab^-1 = 2*2 = 1 mod 3

[eternal pike]

can anyone help me with numbet theory question,

Find all pairs of positive integers ((a, b)) satisfying
[a^2 - b! = 2024.]

[sterile pumice]

Fate

[eternal pike]

one is (45,1)

i guess the only one

how would u prove it?

[torn escarp]

As soon as b! is divisible by a larger power of 2 than 2024 is divisible by (8), you will always have 2024+b! divisible by exactly 8 and no higher power of 2. But this can never be solved since 2^3 is an odd exponent while a^2 has an even exponent.

[eternal pike]

hmm

i dont think i get it

[torn escarp]

yeah it's pretty confusing to say in words like that haha

in general if you have integers n and m which are are divisible by different powers of a prime number, then n+m is divisible by exactly the lower power of the two primes and not more than that

[eternal pike]

is that some theorem?

[torn escarp]

so 5+25 = 30 is exactly divisible by 5 because 5 is divisible once and 25 twice

[loud maple]

It is trivial to prove

[torn escarp]

the high brow way of calling this is "the p-adic's ultrametric inequality's strong property" lol

[eternal pike]

alright, so how would u formally "solve" the task? that it is just 45 and 1

[loud maple]

They just did

[torn escarp]

find the smallest b so that b! is divisible by a power of 2 larger than 8

then you have to check all those cases up to that point to be sure

[eternal pike]

okay

[torn escarp]

Maybe it helps to look at an example, let's say you pick the large value b=10 then we have a^2 = 2024 +10! = 2^3 * 253 + 2^8 * 14175

Now that we have a^2 = 2^3 * ( 253 + 2^5 * 14175) you can check that (253 + 2^5 * 14175) is odd.

This means whatever power of 2 is dividing a^2 will be 2^3, but 3 is odd while every power of 2 in a^2 will have an even exponent, so it can't be solved.

[west glade]

I would have just said, consider mod 16. seems like the easier perspective

[eternal pike]

thanks

do u know how to do this find all pairs ((x, p)), where (x) is an integer, (p) is a prime number, and they satisfy the equation:

[x^3 + x^2 + x + 1 = p^2.]

[sterile pumice]

Fate

[torn escarp]

good point that's easier. The way I worked it out was literally just |a|^2 = |2024+b!| = |2|^3 (when |2024|>|b!|) with the 2-adic absolute value, so I was trying to make that friendlier but it's too wordy haha

[torn escarp]

what have you tried

[eternal pike]

(1,2)

is 1 solution

the x's must be even

so the +1 makes it odd

wait mby not

[torn escarp]

I'm playing around with factoring it to find a simpler solution. I have proved that this is the only one that works though by other methods

[torn escarp]

yeah that's right cause you already got the only p even solution

[torn escarp]

actually that looks like that solves this looking mod 4 already

[loud maple]

We have (x²+1)(x+1)=p²

So either x²+1=p² and x+1=1 or x²+1=x+1=p

The first case gives x=0 (not possible, since p=1 isn't prime) and the second gives x=1 and p=2

[eternal pike]

ye that is right

[eternal pike]

Prove that the only integer solution to the equation ( x^2 + y^2 + z^2 = 4xyz ) is ( (x, y, z) = (0, 0, 0) ).

[sterile pumice]

Fate

[eternal pike]

@torn escarp

[loud maple]

Suppose there exists another integer solution, then one can prove that x, y, and z are all divisible by 4. Let x=2m, y=2n, z=2l. You will get m²+n²+l²=8mnl

And now repeat

You will get an infinite decreasing sequence of nonzero integer solutions

Which isn't possible

[inner wolf]

on some real shit

came across this problem

I have a hunch that the solution permutation is of the form
$$[1, \cdots, k - 1, n - 1, n - 2, \cdots, k]$$ I'll try to prove it later

[sterile pumice]

Abdullah Zero 🇵🇸

[inner wolf]

thus, the permutation up to 1 ... k-1 is just the sum of first k-1 squares which can be done in O(1) time, but how about the second partition of the permutation?

is there a way to compute the dot product of say [i..j] * [j..i] in constant time?

[lost yacht]

Would anyone like to do a study group for elementary number theory?

[rigid obsidian]

Just wondering: is there any possible use that the Collatz Conjecture could have if proven?

[torn escarp]

possibly any tricks or methods used to solve it would be reused or generalized to tackle similar problems in arithmetic dynamics

[rigid obsidian]

ok

[wooden glen]

The problem itself is not important except for its stubborn resistance to being solved, especially considering how elementary its statement is.

[fading void]

Can I get a tip on this question? I've been able to prove that the common divisor sets of (a,b) and (a, b + ka) are the same, which shows that gcd(a, b) = gcd(a, b + ka) for any a, b, k in Z, but I'm not sure how to proceed from here...

[wooden glen]

I'd reason that gcd(a+b,a-b) = gcd(2a, a-b), and that needs to be either gcd(a, a-b) or 2·gcd(a, a-b).
But that's a bit handwavy, so for an actual proof I expect it would be neater to go for Bezout's identity.

[heady knoll]

With Bezout, you can assume ma + nb = 1, and note that (m+n)(a+b) + (m-n)(a-b) = 2(ma+nb) = 2, so gcd(a+b,a-b) is 1 or 2.

For the other one, note that (2m-n)(2a+b) + (2n-m)(a+2b) = 3(ma + nb)

[fading void]

Good observation

[lofty axle]

This seems like something that should be easy, given $a, b \in \mathbb{N}$, what $m, n \in \mathbb{N}$ satisfies:
$$a^{m+n} \mod b = a^{m} \mod b$$
So we can rearrange this to: $a^m \left( a^n - 1 \right) \mod b = 0$

If b is prime, this seems pretty easy with fermat, m = 1, and n = b

[torn escarp]

This might be cleaned up a bit, but we can split it up with the chinese remainder theorem into all the prime powers of b, then we're solving $a^m(a-1)=0 \mod p^k$ where $k=v_p(b)$.

[sterile pumice]

Merosity

[torn escarp]

nice thing is this means when $v_p(a)>0$ we have to have $m \ge \frac{v_p(b)}{v_p(a)}$ and when $v_p(a)=0$ we have $ord_{p^k}(a) | n$

[sterile pumice]

Merosity

[torn escarp]

so that completely answers it, although I didn't really explain how I came to that

I can go through the details if you want, or if you wanna try working through some of that on your own as mod p^k now

[lofty axle]

Yes you didn't but I think that does answer it. I'll need to try get the details down here.
Here k = v_p(b) means, in b's factorization how many powers of p appears in it.

[torn escarp]

yeah, so like b=12 let's say, v_2(12)=2 and v_3(12)=1

the main trick I'm leaning on is v_p(a) =0 or >0 splits into entirely distinct cases and handling those from there is "easy" after that

[lofty axle]

Also your saying:

If $s \mod t = 0$, where $t$ has prime factors $p_1^{k_1}, p_2^{k_2}, \dots$

Then we can be split the problem with CRT into

$s \mod p_1^{k_1} = 0$, $s \mod p_2^{k_2} = 0$ and so on

[torn escarp]

yeah exactly

[lofty axle]

What does ord_{p^k} denote here?

[fading void]

I'm trying to interpret this question:

I don't know what "gcd(a, b) = d for any d in Z+" means

[torn escarp]

ord_m(a) means the smallest number r you can pick to make a^r=1 mod m

[lofty axle]

Ah right

[fading void]

Does anyone actually know what it's asking us to prove here?

[lofty axle]

Yeah, so it's saying, if for any d, we have gcd(a,b) = d and we can find an (x,y) such that ax + by = d, then gcd(x, y) = 1

[fading void]

Ok, since gcd(a, b) is a fixed number, then for all but one d value this is like a F => T type statement?

[lofty axle]

I'm guessing since d is a common divisor of a and b, we can divide ax + by = d by d?

[fading void]

Yeah, I get the algebra, but I'm having trouble parsing the statement

Like we can totally remove d and just replace it by gcd(a, b) right?

[wooden glen]

Yeah.

[lofty axle]

I read the statement is, given some a, b, d such that satisfies: gcd(a, b) = d and ax + by = d

Show that gcd(x, y) = 1, I might be wrong though.

[fading void]

if d != gcd(a, b) then it holds vacuously so I think we can throwaway d though

[wooden glen]

The problem statement is somehat confusingly worded with the "for any d in Z+" in the middle of the sentence.

[lofty axle]

Yeah, it makes d and a,b's relation seem weird.

What it should be that some a,b,d where gcd(a,b) = d or for any a,b let gcd(a,b) = d

[fading void]

Hmm, also interestingly I believe we can prove this without the algebra

[wooden glen]

But from a bit of experience, I'm pretty sure it should be interpreted as:

Show for every d in Z+ that if gcd(a,b)=d and ax+by=d, then ...

[fading void]

since gcd(a, b) = 1, there exist x, y st ax + by = 1, but changing roles of a ,x and b, y, we've found a linear combination of x, y that yield 1, so gcd(x, y) = 1 as well, does this seem valid?

[lofty axle]

I don't think your allowed to assume gcd(a,b) = 1

[fading void]

Ah I see my bad

Right, so I guess we do need that bit of algebra

Along the same lines I wanted to prove that {ax + by : x, y in Z} is the set of all integral multiple of gcd(a, b). For simplicity let g := gcd(a, b), then for any ax + by, then we have that (a/g)x + (b/g) y where a/g, b/g, in Z, does this prove the claim?

[lofty axle]

I believe you have proved it. It depends on how detailed you want your proof, but you can also try to prove a/g is in Z and why it implies gcd(x,y)=1, though some might consider it trivial.

[fading void]

Sorry in the question I just posed, it's certainly possible that gcd(x, y) != 1

I'm trying to show that set {ax + by: x, y in Z} (e.g. x = y = 2 works) is the set of all integral multipesl of gcd(a, b)

[lofty axle]

Oh this is a different question from this one?

[fading void]

Yes, this is a new one

[lofty axle]

Oh okay.

[fading void]

It just used some similar algebra

I was just trying to say given any ax + b y in that set, we know that g divides it by our previous observation

But I think more work is required because we need to show we can get any multiple, so for example the multiple 5g, we would need to show thats in our set S

I think I have it now.

[lofty axle]

This proves that if an elements is in S, then it is an integer multiple of gcd(a,b).
To prove that if we have an integer multiple of gcd(a,b), then it is in S, it's just applying Bezout and multiplying.

Symbolically, you've proven: r ∈ S → gcd(a,b) | r
but not: gcd(a,b) | r → k ∈ S

[lofty axle]

Genuinely have no idea how someone comes up with this so quickly.

[torn escarp]

you are what you eat,

[fading void]

Looking at this one:

I'm not sure if this question is wrong or if I'm interpreting it wrong, but if say a = 3, and b = 5, then wouldn't 3, 8, 13 all of the same remainder when divided by b = 5? If that's the case, does anyone know what they actually meant here?

[torn escarp]

they're wrong, since all the integers are a+bn, they're all a mod b.

I'm not really sure which direction they wanted to go with it, I'm thinking they meant a, 2a, 3a, 4a, ..., (b-1)a all mod b

I'd bet that's what they meant, and if they didn't, it's still a very useful thing to know

[fading void]

Yeah I think that's correct, I'll try proving that one

[buoyant mason]

x^2 y^2 and z^2 need to be 0 mod 4

if any are 1 mod 4 then their sum is 1, 2, or 3 mod 4