# Verify that ## 17 ## divides ## 11^{104}+1 ##

• Math100
In summary, by using Fermat's theorem, it was proved that 17 divides 11^{104}+1. This was done by setting a=11, p=17 and using the fact that 11^{17-1}\equiv 1\pmod {17}. The additional calculation (11^2)^4\equiv (121)^4\equiv 2^4\equiv 16\pmod{17} was also given to show that (11^2)^4 \equiv 16\pmod{17}. Additionally, it was mentioned that this proof could also be done directly using repeated modular arithmetic without Fermat's theorem.
Math100
Homework Statement
Use Fermat's theorem to verify that ## 17 ## divides ## 11^{104}+1 ##.
Relevant Equations
None.
Proof:

Fermat's theorem states:
Let ## p ## be a prime and suppose that ## p\nmid a ##. Then ## a^{p-1}\equiv 1\pmod {p} ##.
By using Fermat's theorem, we will prove that ## 17 ## divides ## 11^{104}+1 ##.
Suppose ## a=11, p=17 ## and ## p\nmid a ##.
Then ## 11^{17-1}\equiv 1\pmod {17}\implies 11^{16}\equiv 1\pmod {17} ##.
Observe that ## 104=16\cdot 6+8 ##.
This means
\begin{align*}
&11^{104}\equiv 11^{16\cdot 6+8}\equiv [(11^{16})^{6}\cdot 11^{8}]\pmod {17}\\
&\equiv [1^{6}(11^{2})^{4}]\pmod {17}\equiv 16\pmod {17}.\\
\end{align*}
Thus ## 11^{104}+1\equiv 0\pmod {17}\implies 17\mid (11^{104}+1) ##.
Therefore, ## 17 ## divides ## 11^{104}+1 ##.

You could have given me an additional calculation ##(11^2)^4\equiv (121)^4\equiv 2^4\equiv 16\pmod{17}## as it is not immediately clear that ##(11^2)^4 \equiv 16\pmod{17}.## On the other hand, maybe it is just the time difference, will say already evening over here.

That's all. The rest is fine.

Math100 and SammyS
fresh_42 said:
You could have given me an additional calculation ##(11^2)^4\equiv (121)^4\equiv 2^4\equiv 16\pmod{17}## as it is not immediately clear that ##(11^2)^4 \equiv 16\pmod{17}.##

That's all. The rest is fine.
I apologize. I always tend to skip a few steps when writing proofs.

fresh_42
It's a bad habit and I must abandon this vice.

Math100 said:
It's a bad habit and I must abandon this vice.
Don't mind. I was just lazy. Your proof is well written so it can be read fluently, except that nobody knows what ##11^8## is.

Math100
nice job. note that it is also fairly easy to do this directly by repeated modular arithmetic, without fermat, using that 11 is -6, mod 17, and 6 is 2 times 3 and 2^4 is -1, and 3^4 is -4, hence 3^8 is -1, mod 17. hence (11)^104 is -1, mod 17.

jim mcnamara

## What does it mean to "verify" that 17 divides 11^104+1?

To "verify" means to prove or confirm that something is true or correct. In this case, we want to prove that 17 is a divisor of the number 11^104+1, meaning that 11^104+1 is evenly divisible by 17 without any remainder.

## How do you calculate 11^104+1?

To calculate 11^104+1, you can use a calculator or a computer program. Alternatively, you can use the exponentiation by squaring method, which involves breaking down the exponent into smaller, more manageable exponents.

## Why is 17 chosen as the divisor in this problem?

The number 17 is chosen as the divisor in this problem because it is a prime number, meaning it is only divisible by 1 and itself. This makes it a good number to use in divisibility tests. Additionally, 17 is a factor of 11^104+1, meaning it evenly divides into the number without any remainder.

## How do you prove that 17 divides 11^104+1?

To prove that 17 divides 11^104+1, you can use the division algorithm, which states that if a number is divisible by another number, then the remainder will be 0. In this case, if we divide 11^104+1 by 17, the remainder is 0, therefore proving that 17 is a divisor of 11^104+1.

## What is the significance of this problem in mathematics?

This problem is significant in mathematics because it demonstrates the concept of divisibility and how to prove that a number is a divisor of another number. It also showcases the use of prime numbers and the division algorithm. Additionally, this problem has applications in number theory and modular arithmetic.

• Precalculus Mathematics Homework Help
Replies
2
Views
727
• Precalculus Mathematics Homework Help
Replies
14
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
2K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
14
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
9
Views
1K