1

I don't know if I'm correct, since I didn't even have to use the hint. So I'm asking for proof verification since I am also not too confident on primes.

Suppose $\gcd(a, 35) = 1.$ Show that $a^{12} - 1$ is divisible by $35$.

Here's the hint that wasn't applied. How would I have applied it?

(HINT) Factor $12$ as $2*6$ and apply Fermat's Little Theorem for $p = 7$. Then factor as $4*3$ and use $p = 5$.

We want to show $35\mid a^{12}-1$, equivalent to $$a^{12} \equiv 1 = 1 \pmod{35}$$

So $(a^{12})^2 = a^{24} \equiv 1^2 = 1 \pmod{35}$ as well. But $\phi(35) = 24$, and $a, 35$ are coprime numbers - so by Fermat's Little Theorem, we have $35\mid a^{12}-1$.

Here is another one:

Use Fermat's Little Theorem to find the unit digit of $3^{100}$.

(HINT) Use $p = 5$ and consider parity.

Assume

$$3^{100} \equiv a \pmod 5$$

But we have $3^2 \equiv -1 \pmod 5$ so $3^{100} \equiv 1 \pmod 5$. Thus the units digit is $1$.

Community
  • 1
Don Larynx
  • 4,703
  • Fixed @Clayton. – Don Larynx Sep 24 '13 at 12:42
  • 1
    In the first part you make the basic logic error of deriving something from the (sought) conclusion, and proving that instead of the result asked for. It doesn't work that way. Suppose you wanted to prove the obviously wrong $a\equiv 1\pmod{35}$. Then it would follow that $a^{24}\equiv 1^{24}=1\pmod{35}$ which is true by Fermat. But $a\equiv 1\pmod{35}$ is still false. – Marc van Leeuwen Sep 24 '13 at 12:55
  • @MarcvanLeeuwen: I think everything except her conclusion that $35\mid a^{12}-1$ is correct. See the comments beneath my answer with Cameron Buie. – Clayton Sep 24 '13 at 13:26
  • 1
    @Clayton: Since the thing asked to be proved is in fact true, anything derived from it will also turn out to be true. But it does not amount to a valid reasoning. The point is not that false things are being said, but that invalid deductions are made. Things can be repaired, but one first needs to realise the fundamental error. – Marc van Leeuwen Sep 24 '13 at 14:00
  • @MarcvanLeeuwen: I believe she is using Euler's theorem before she makes her conclusion, so what she has said isn't derived from what she is trying to prove. Rather, it is derived from some other information which she already knows is true. – Clayton Sep 24 '13 at 14:04
  • @Clayton: Clearly the Fermat-Euler theorem is being used (calling it Fermat's Little Theorem), but this is after the exponent $12$ has been changed to $24$ (and indeed for $12$ it would not apply). It is that change that is a derivation from what has to be proved. It says clearly "$a^{12}\equiv 1$ so $(a^{12})^2\equiv1^2=1$"; a valid implication, but in the wrong direction, as it starts with the conclusion sought. – Marc van Leeuwen Sep 24 '13 at 14:17
  • @MarcvanLeeuwen So can I keep working backward until I get to my hypothesis - and then work forward? – Don Larynx Sep 24 '13 at 15:33
  • Yes, you can work backward from the conclusion, and this is sometimes a good strategy. Like "in order to conclude, it would suffice to have this and that, for which it would suffice..." Of course you must carefully choose the intermediate steps; they might be sufficient but false. If you know necessary and sufficient conditions, that is safe. In this case having the right remainder mod 5 and mod 7 is necessary and sufficient – Marc van Leeuwen Sep 24 '13 at 16:54
  • @MarcvanLeeuwen: We'll just agree that we read it differently :) I put the pieces of the "puzzle" together in a different order. – Clayton Sep 24 '13 at 17:33

1 Answers1

1

Hint: Fermat's Little Theorem says $a^{p-1}\equiv1\pmod{p}$. So, $a^{12}-1=(a^4)^3-1\equiv0\pmod{5}$, i.e., $5\mid a^{12}-1$. Can you show $7\mid a^{12}-1$ and make the desired conclusion?

Your proof shows $(a^{12}+1)(a^{12}-1)\equiv0\pmod{35}$, but I don't think you can make the desired conclusion from this fact.

Clayton
  • 24,751
  • I have another one up there.. Also, How so? – Don Larynx Sep 24 '13 at 12:49
  • @Jossie: You'll need to post the second question as a separate post. What is your second question? – Clayton Sep 24 '13 at 12:50
  • I just feel as if I'm "wasting bandwidth" with my post. It is rather simple to verify.

    How so is it that the proof shows 35∣a12+1 or 35∣a12−1?

     – Don Larynx Sep 24 '13 at 12:50
  • @Jossie: Ah, I didn't see you just wanted verification. Yes, it looks okay (not sure if it is necessary, but maybe argue $6$ is not in the group generated by $3$ modulo $10$). – Clayton Sep 24 '13 at 12:52
  • In fact, Jossie's proof does not show that $(a^{12}+1)(a^{12}-1)\equiv 0\pmod{35}.$ It assumes the conclusion in the middle, so it does not show anything but a necessary (though irrelevant) condition for the conclusion to hold. As for the second one, the argument definitely needs to be made why the unit digit can't be $6$. – Cameron Buie Sep 24 '13 at 13:07
  • I stand corrected. Since $\operatorname{gcd}(a,35)=1,$ then indeed we have by Euler's Theorem that $a^{24}=a^{\varphi(35)}\equiv 1\pmod{35}.$ I guess it remains only to show that $a^{12}\not\equiv-1\pmod{35}.$ – Cameron Buie Sep 24 '13 at 13:18
  • @CameronBuie: I am making the assumption this is available, but it is the only place I could see why Jossie would bring up $\varphi(35)=24$. – Clayton Sep 24 '13 at 13:20
  • I'm not sure why it's brought up either, but it seems that Jossie is concluding that $a^{24}\equiv1\pmod{35}$ from $a^{12}\equiv1\pmod{35},$ instead. – Cameron Buie Sep 24 '13 at 13:22
  • We read it differently I suppose. I assumed she thought along the lines of what I have written above, and somehow concluded $35\nmid a^{12}+1$. If it can be excluded, I don't immediately see how to do it. (Also, she mentions $a$ and $35$ are coprime, simply as fuel for my interpretation and the use of Euler's Theorem). – Clayton Sep 24 '13 at 13:25
  • So basically I would get half credit on a test? I think I have the right idea. – Don Larynx Sep 24 '13 at 19:01