Solving a Number Theory Problem Using Fermat's Little Theorem

Click For Summary

Homework Help Overview

The discussion revolves around a number theory problem involving modular arithmetic, specifically the calculation of \(2^{70} + 3^{70} \mod 13\) using Fermat's Little Theorem.

Discussion Character

  • Exploratory, Conceptual clarification, Mathematical reasoning

Approaches and Questions Raised

  • The original poster attempts to apply Fermat's Little Theorem to simplify the exponent, while expressing uncertainty about the next steps. Other participants explore the properties of powers and inquire about the validity of a proposed factorization involving \(4^5 + 9^5\).

Discussion Status

The discussion is ongoing, with participants sharing insights about relevant formulas and properties of exponents. Some guidance has been offered regarding the relationship between \(a^n + b^n\) and \(a^n - (-b)^n\), but no consensus has been reached on the approach to take next.

Contextual Notes

Participants are working under the constraints of a homework problem, which may limit the information they can use or the methods they can apply.

ehrenfest
Messages
2,001
Reaction score
1

Homework Statement


http://math.stanford.edu/~vakil/putnam07/07putnam2.pdf

I am working on number 2.
So I want to find 2^70 + 3^70 mod 13.
I can use Fermat's Little Theorem to reduce the exponent to 10, but I do not know what to do next...


Homework Equations





The Attempt at a Solution

 
Physics news on Phys.org
2^2 = 4 and 3^2 = 9

and 4^5 + 9^5 = (4+9)*something.
 
morphism said:
4^5 + 9^5 = (4+9)*something.
Is that true? Where does that come from?
 
You know how there's a formula for a^n - b^n? Well, there's also one for a^n + b^n when n is odd. (a^n + b^n = a^n - (-b)^n.)
 
I see. Thanks.
 

Similar threads

Insights Fermat's Last Theorem
  • · Replies 105 ·
4
Replies
105
Views
11K
Find all odd n such that n|3^{n}+1
  • · Replies 9 ·
Replies
9
Views
5K
Proving Divisibility Using Fermat's Theorem
  • · Replies 4 ·
Replies
4
Views
3K
Application of Fermat's Little Theorem
  • · Replies 6 ·
Replies
6
Views
2K
Proving Total Order of Integers through LCM and GCD Relationship
  • · Replies 2 ·
Replies
2
Views
3K
AMGM(n): Solving Problem 8 Part B
  • · Replies 6 ·
Replies
6
Views
2K
Fermat Number Proof: Relatively Prime
  • · Replies 4 ·
Replies
4
Views
2K
Congruence identities using Fermat's Little Theorem
  • · Replies 3 ·
Replies
3
Views
3K
Using Modular Arithmetic to Solve Congruence Equations
  • · Replies 11 ·
Replies
11
Views
2K
Number 6: Differences between Numbers in Pigeon Holes
  • · Replies 3 ·
Replies
3
Views
2K