I am pretty much stuck, since smaller examples are impossible to find, nor does this seem like an induction question. I am thinking of using proof by contradiction, but don't know where to find the contradiction. I also struggle to recall the theorem that may help me answer this problem.
Asked
Active
Viewed 130 times
2 Answers
0
Let $a=24^{100}-1$, $a$ is clearly not a square. We conclude that the number of divisors of $a$ is even. Since $24^{100}-1$ is $-1\bmod 3$ we conclude that if $d$ is a divisor of $a$ then $a/d$ is congruent to $-d\bmod 3$. We conclude $\sigma(a)$ is a multiple of $3$.
For the second step notice $\sigma(a)=\sigma(24^{50}+1)\sigma(24^{25}-1)\sigma(24^{25}+1)$.
We can see every factor is even by the same pairing up trick.
Asinomás
- 105,651
-
Would it not be 2 mod 3? – Gerard L. Oct 28 '17 at 00:57
-
$d+a/d\equiv d-d\bmod 3$. – Asinomás Oct 28 '17 at 00:57
-
Notice that $1/d\equiv d$ when working $\bmod 3$. – Asinomás Oct 28 '17 at 00:58
-
because $24^{100}$ is a square – Asinomás Oct 28 '17 at 00:59
-
Although the one that is not so clear that it is not a square is $24^{25}+1$ – Asinomás Oct 28 '17 at 00:59
-
$24^{100}$ is 0 mod 3, so subtracting one would give you 2 mod 3. – Gerard L. Oct 28 '17 at 00:59
-
I didn't understand your last comment – Asinomás Oct 28 '17 at 01:00
-
Oh ok, that is another way of proving it is not a square – Asinomás Oct 28 '17 at 01:00
-
But it is not 1 mod 3 as you state – Gerard L. Oct 28 '17 at 01:01
-
And would you explain your sigma notation to me? Is it just simply a function for your "pairing" or does it have a designated meaning? – Gerard L. Oct 28 '17 at 01:02
-
the $-1$ part was a typo. $\sigma(n)$ is the usual notation for the sum of the divisors of $n$. In the second step we are using that $\sigma$ is multiplicative – Asinomás Oct 28 '17 at 01:02
-
Could you explain your "Since 24^100−1 is −1mod3 we conclude that if dd is a divisor of a then a/d is congruent to −dmod3?" I'm a little confused – Gerard L. Oct 28 '17 at 01:05
-
And I don't see how your answer shows that the sum of the divisors sums to a multiple of 24 – Gerard L. Oct 28 '17 at 01:06
0
Note that, if $mn = 24^{100} - 1$, then $mn = -1$ modulo $24$. In particular, $m$ and $n$ are invertible modulo $24$, and $m = -n^{-1}$. Note also that, modulo $24$, we have $$1^2 = 5^2 = 7^2 = 11^2 = 13^2 = 17^2 = 19^2 = 23^2 = 1,$$ which means that $mn = -1$ implies that $m + n = 0$ modulo $24$. It also implies that $m \neq n$ as they are in different modulo classes. Thus, all divisors sum to a multiple of $24$, as they form pairs of numbers which sum to a multiple of $24$.
Theo Bendit
- 50,900
-
What do you mean by invertible? And how do your examples prove your third statement about mn=-1 mod 24? – Gerard L. Oct 28 '17 at 01:10
-
I mean, $m$ is invertible if there is some $n$ such that $mn = 1$ modulo $24$, which is the multiplicative identity. That is, $m$ has a multiplicative inverse (basically meaning the gcd of $m$ and $24$ is $1$). – Theo Bendit Oct 28 '17 at 01:11
-
Since every invertible modulo class $n$ has the property that $n^2 = 1$, it follows that $n = n^{-1}$. So, if $mn = -1$, then $m = (-1)n^{-1} = -n$, hence $m + n = 0$. – Theo Bendit Oct 28 '17 at 01:14
-
-
By "modulo class", I mean a number modulo $24$. I don't like to refer to a specific number (say $5$), because $5$ is a different number to, say, $29$, but I'm referring to the same modulo class: $$\lbrace \ldots, -18, 5, 29, \ldots \rbrace.$$ Whenever you're performing operations on numbers modulo another number, you're really performing operations on the entire modulo class. – Theo Bendit Oct 28 '17 at 01:24