3
$\begingroup$

I'm working my way through The Mathematical Olympiad Handbook by A. Gardiner.

In the section A little useful mathematics right at the start the following basic identities are laid out

  • $x^n -1 = (x-1)(x^{n-1} + ... + 1)$

  • $x^n - y^n = (x-y)(x^{n-1} + ... + y^{n-1})$

  • $x^n + 1 = (x+1)(x^{n-1} + ... + 1)$

  • $x^n + y^n = (x-y)(x^{n-1} + ... + y^{n-1})$

In this context the following two exercises are posed

  1. Prove $2^{55} + 1$ is divisible by $33$
  2. Prove $1900^{1990} -1$ is divisible by $1991$

So for (1) the strong implication seems to be to somehow use the fact that $33=2^5+1=(2+1)(2^4-2^3+2^2-2^1+1)$ and use that, but other than realising that I am slightly lost.

I can see using Fermat's Little Theorem allows an attack ($2^{55}=(2^5)^{11}$ etc.) but how to do it with just those identities I can't see it as Fermat's Little Theorem is used later as a second proof of this problem in the number theory section.

Can anyone see how to do it?

$\endgroup$
8
  • $\begingroup$ Hint for $1.$ : Show that divisibility by $3$ and by $11$ $\endgroup$
    – Peter
    Dec 19, 2020 at 14:28
  • $\begingroup$ @Peter I believe OP wants it done via the "basic identities that are laid out" rather than "Fermat's Little Theorem that comes later". $\endgroup$
    – Calvin Lin
    Dec 19, 2020 at 14:30
  • $\begingroup$ @CalvinLin The approach also works without FLT. I admit that here we can do better. $\endgroup$
    – Peter
    Dec 19, 2020 at 14:31
  • $\begingroup$ @Peter Interesting. I get the $ 2+1 = 3$. Can you write up how to show it is divisible by 11 (without showing 33 directly)? $\endgroup$
    – Calvin Lin
    Dec 19, 2020 at 14:32
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Peter
    Dec 19, 2020 at 14:36

3 Answers 3

Reset to default
5
$\begingroup$

Hint:

$$2^{55} +1 =(2^5)^{11} +1 = 32^{11} +1 = (32+1)(\dots) $$ using your third identity.

$\endgroup$
6
  • $\begingroup$ Thanks seems so obvious now. I am struggling to use a similar technique to crack $1900^{1990}-1$ divisible by 1991. Any idea? $\endgroup$
    – Gau55man
    Dec 19, 2020 at 14:40
  • 1
    $\begingroup$ @Gau55man Have you copied down the problem correctly? Wolfram says that is not true wolframalpha.com/input/… $\endgroup$
    – Vishu
    Dec 19, 2020 at 14:53
  • $\begingroup$ Yes I've triple checked $1900^{1990} -1$ is divisible by 1991. Most sensible pattern would mean what was intended was $1990^{1990}-1$ is divisible by $1991$ I'm guessing. $\endgroup$
    – Gau55man
    Dec 19, 2020 at 16:38
  • $\begingroup$ @Gau55man What have you checked it with? $\endgroup$
    – Vishu
    Dec 19, 2020 at 18:01
  • $\begingroup$ I meant I tripled checked that is what the questions says so there is a typo/mistake in my book. I'm assuming intention is $1990^{1990} -1$ which admits solution by recognising as others have that $(1990^2)^{955} -1 = (1990^2 - 1)(...)$ then using identity $n^2 -1=(n+1)(n-1)$ which gives $1990^2 -1=1991 \cdot 1989$ showing that 1991 is a factor. $\endgroup$
    – Gau55man
    Dec 19, 2020 at 22:35
3
$\begingroup$

$$(2^{5})^{11} + 1 = 32^{11} + 1 \overset * \equiv (-1)^{11} + 1 = 0 \pmod{33}$$ $(*)$: $32 = 33 - 1 \equiv -1 \pmod {33}$

$\endgroup$
1
$\begingroup$

For divisibility of $2^{55}+1$ by $33,$ we can write $$2^{55}+1=(2^{5})^{11}+1=(33-1)^{11}+1,$$ and apply the third identity.

Isn't there a typo in the second exercise? I suggest to prove divisibility of $1990^{1990} -1$ by $1991$ instead. We have
$$1990^2 -1=1991\times 1989$$ and use the first identity.

$\endgroup$
2
  • 1
    $\begingroup$ $1900^2-1 \ne 1991\times 1989 $ $\endgroup$
    – Vishu
    Dec 19, 2020 at 14:53
  • 1
    $\begingroup$ You're right. I was rewriting it while you were posting your comment. Then I noticed you also think there is a typo in OP. $\endgroup$
    – user376343
    Dec 19, 2020 at 15:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .