Find the largest power of 3 that divides $N =19202122…919293$. [closed]

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

Question

All the numbers from $19$ to $93$ are written consecutively to form the number $N =19202122...........919293$. Find the largest power of $3$ that divides $N$.

The following hint has been provided.

The square of any integer is either divisible by $4$ or leaves a remainder $1$ divided by $4$. Thus, an integer which leaves a remainder $2$ or $3$ when divided by $4$ can never be a square. If a prime p divides a square number the $p^2$ also divides that number.

number-theory prime-numbers

share|cite|improve this question

edited Jul 28 at 12:44

Mythomorphic

5,0811732

asked Jul 28 at 12:41

Whosethat

6

closed as off-topic by amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister Jul 29 at 0:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  What is your attempt?
  – Mythomorphic
  Jul 28 at 12:43
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  1 st power of 3 only
  – Ninja hatori
  Jul 28 at 13:00
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

Question

All the numbers from $19$ to $93$ are written consecutively to form the number $N =19202122...........919293$. Find the largest power of $3$ that divides $N$.

The following hint has been provided.

The square of any integer is either divisible by $4$ or leaves a remainder $1$ divided by $4$. Thus, an integer which leaves a remainder $2$ or $3$ when divided by $4$ can never be a square. If a prime p divides a square number the $p^2$ also divides that number.

number-theory prime-numbers

share|cite|improve this question

edited Jul 28 at 12:44

Mythomorphic

5,0811732

asked Jul 28 at 12:41

Whosethat

6

closed as off-topic by amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister Jul 29 at 0:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  What is your attempt?
  – Mythomorphic
  Jul 28 at 12:43
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  1 st power of 3 only
  – Ninja hatori
  Jul 28 at 13:00
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

Question

All the numbers from $19$ to $93$ are written consecutively to form the number $N =19202122...........919293$. Find the largest power of $3$ that divides $N$.

The following hint has been provided.

The square of any integer is either divisible by $4$ or leaves a remainder $1$ divided by $4$. Thus, an integer which leaves a remainder $2$ or $3$ when divided by $4$ can never be a square. If a prime p divides a square number the $p^2$ also divides that number.

number-theory prime-numbers

share|cite|improve this question

edited Jul 28 at 12:44

Mythomorphic

5,0811732

asked Jul 28 at 12:41

Whosethat

6

Question

All the numbers from $19$ to $93$ are written consecutively to form the number $N =19202122...........919293$. Find the largest power of $3$ that divides $N$.

The following hint has been provided.

The square of any integer is either divisible by $4$ or leaves a remainder $1$ divided by $4$. Thus, an integer which leaves a remainder $2$ or $3$ when divided by $4$ can never be a square. If a prime p divides a square number the $p^2$ also divides that number.

number-theory prime-numbers

share|cite|improve this question

edited Jul 28 at 12:44

Mythomorphic

5,0811732

asked Jul 28 at 12:41

Whosethat

6

share|cite|improve this question

share|cite|improve this question

edited Jul 28 at 12:44

Mythomorphic

5,0811732

edited Jul 28 at 12:44

Mythomorphic

5,0811732

edited Jul 28 at 12:44

Mythomorphic

5,0811732

5,0811732

asked Jul 28 at 12:41

Whosethat

6

asked Jul 28 at 12:41

Whosethat

6

asked Jul 28 at 12:41

Whosethat

6

6

closed as off-topic by amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister Jul 29 at 0:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister Jul 29 at 0:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – amWhy, Jyrki Lahtonen, Xander Henderson, José Carlos Santos, Adrian Keister

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  What is your attempt?
  – Mythomorphic
  Jul 28 at 12:43
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  1 st power of 3 only
  – Ninja hatori
  Jul 28 at 13:00
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  What is your attempt?
  – Mythomorphic
  Jul 28 at 12:43
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  1 st power of 3 only
  – Ninja hatori
  Jul 28 at 13:00
  

  
  
  
  

1

1

What is your attempt?
– Mythomorphic
Jul 28 at 12:43

What is your attempt?
– Mythomorphic
Jul 28 at 12:43

1

1

1 st power of 3 only
– Ninja hatori
Jul 28 at 13:00

1 st power of 3 only
– Ninja hatori
Jul 28 at 13:00

add a comment | 

2 Answers
2

active

oldest

votes

up vote
2
down vote

With a bit more rigour and without a calculator, we have:

$$N =sum_k=0^93-19 (93-k)cdot 10^2k$$

Now if we inspect this $bmod 9$ we can use the fact that $10^j equiv 1 mod 9$ to find:

$$N equivsum_k=0^74 (93-k) mod 9$$
$$N equiv 75cdot 93 - sum_k=0^74 k mod 9$$
$$N equiv 3cdot 3 - frac12cdot 74cdot 75 mod 9$$
$$N equiv 9 - 37cdot 3 mod 9$$
$$N equiv 9 - 1cdot 3 mod 9$$
$$N equiv 6 mod 9$$

Thus we know that $N$ is not divisible by $9$. But since $(N bmod 9) equiv N mod 3$ we can re-use the above calculation to immediately find that $N equiv 0 mod 3$ and thus is divisible by $3$. That is the largest power of $3$ that divides $N$.

share|cite|improve this answer

answered Jul 28 at 13:30

orlp

6,5951228

add a comment | 

up vote
1
down vote

First of all calculate sum of digits that sum of natural numbers from 19 to 93 which is 4200. It is divisible by 3 but not 9. For divisibility of higher power it has to be divisible by 9 but it is not divisible by 9. So higher power should be 1.

share|cite|improve this answer

answered Jul 28 at 13:07

Ninja hatori

105113

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Brilliant! Wonder how it could be done if the sum were divisible by $9$
  – rsadhvika
  Jul 28 at 13:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @rsadhvika hint might help.
  – Ninja hatori
  Jul 28 at 13:41
  

  
  
  
  

add a comment | 

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

With a bit more rigour and without a calculator, we have:

$$N =sum_k=0^93-19 (93-k)cdot 10^2k$$

Now if we inspect this $bmod 9$ we can use the fact that $10^j equiv 1 mod 9$ to find:

$$N equivsum_k=0^74 (93-k) mod 9$$
$$N equiv 75cdot 93 - sum_k=0^74 k mod 9$$
$$N equiv 3cdot 3 - frac12cdot 74cdot 75 mod 9$$
$$N equiv 9 - 37cdot 3 mod 9$$
$$N equiv 9 - 1cdot 3 mod 9$$
$$N equiv 6 mod 9$$

Thus we know that $N$ is not divisible by $9$. But since $(N bmod 9) equiv N mod 3$ we can re-use the above calculation to immediately find that $N equiv 0 mod 3$ and thus is divisible by $3$. That is the largest power of $3$ that divides $N$.

share|cite|improve this answer

answered Jul 28 at 13:30

orlp

6,5951228

add a comment | 

up vote
2
down vote

With a bit more rigour and without a calculator, we have:

$$N =sum_k=0^93-19 (93-k)cdot 10^2k$$

Now if we inspect this $bmod 9$ we can use the fact that $10^j equiv 1 mod 9$ to find:

$$N equivsum_k=0^74 (93-k) mod 9$$
$$N equiv 75cdot 93 - sum_k=0^74 k mod 9$$
$$N equiv 3cdot 3 - frac12cdot 74cdot 75 mod 9$$
$$N equiv 9 - 37cdot 3 mod 9$$
$$N equiv 9 - 1cdot 3 mod 9$$
$$N equiv 6 mod 9$$

Thus we know that $N$ is not divisible by $9$. But since $(N bmod 9) equiv N mod 3$ we can re-use the above calculation to immediately find that $N equiv 0 mod 3$ and thus is divisible by $3$. That is the largest power of $3$ that divides $N$.

share|cite|improve this answer

answered Jul 28 at 13:30

orlp

6,5951228

add a comment | 

up vote
2
down vote

up vote
2
down vote

With a bit more rigour and without a calculator, we have:

$$N =sum_k=0^93-19 (93-k)cdot 10^2k$$

Now if we inspect this $bmod 9$ we can use the fact that $10^j equiv 1 mod 9$ to find:

$$N equivsum_k=0^74 (93-k) mod 9$$
$$N equiv 75cdot 93 - sum_k=0^74 k mod 9$$
$$N equiv 3cdot 3 - frac12cdot 74cdot 75 mod 9$$
$$N equiv 9 - 37cdot 3 mod 9$$
$$N equiv 9 - 1cdot 3 mod 9$$
$$N equiv 6 mod 9$$

Thus we know that $N$ is not divisible by $9$. But since $(N bmod 9) equiv N mod 3$ we can re-use the above calculation to immediately find that $N equiv 0 mod 3$ and thus is divisible by $3$. That is the largest power of $3$ that divides $N$.

share|cite|improve this answer

answered Jul 28 at 13:30

orlp

6,5951228

With a bit more rigour and without a calculator, we have:

$$N =sum_k=0^93-19 (93-k)cdot 10^2k$$

Now if we inspect this $bmod 9$ we can use the fact that $10^j equiv 1 mod 9$ to find:

$$N equivsum_k=0^74 (93-k) mod 9$$
$$N equiv 75cdot 93 - sum_k=0^74 k mod 9$$
$$N equiv 3cdot 3 - frac12cdot 74cdot 75 mod 9$$
$$N equiv 9 - 37cdot 3 mod 9$$
$$N equiv 9 - 1cdot 3 mod 9$$
$$N equiv 6 mod 9$$

Thus we know that $N$ is not divisible by $9$. But since $(N bmod 9) equiv N mod 3$ we can re-use the above calculation to immediately find that $N equiv 0 mod 3$ and thus is divisible by $3$. That is the largest power of $3$ that divides $N$.

share|cite|improve this answer

answered Jul 28 at 13:30

orlp

6,5951228

share|cite|improve this answer

share|cite|improve this answer

answered Jul 28 at 13:30

orlp

6,5951228

answered Jul 28 at 13:30

orlp

6,5951228

answered Jul 28 at 13:30

orlp

6,5951228

6,5951228

add a comment | 

add a comment | 

up vote
1
down vote

First of all calculate sum of digits that sum of natural numbers from 19 to 93 which is 4200. It is divisible by 3 but not 9. For divisibility of higher power it has to be divisible by 9 but it is not divisible by 9. So higher power should be 1.

share|cite|improve this answer

answered Jul 28 at 13:07

Ninja hatori

105113

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Brilliant! Wonder how it could be done if the sum were divisible by $9$
  – rsadhvika
  Jul 28 at 13:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @rsadhvika hint might help.
  – Ninja hatori
  Jul 28 at 13:41
  

  
  
  
  

add a comment | 

up vote
1
down vote

First of all calculate sum of digits that sum of natural numbers from 19 to 93 which is 4200. It is divisible by 3 but not 9. For divisibility of higher power it has to be divisible by 9 but it is not divisible by 9. So higher power should be 1.

share|cite|improve this answer

answered Jul 28 at 13:07

Ninja hatori

105113

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Brilliant! Wonder how it could be done if the sum were divisible by $9$
  – rsadhvika
  Jul 28 at 13:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @rsadhvika hint might help.
  – Ninja hatori
  Jul 28 at 13:41
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

First of all calculate sum of digits that sum of natural numbers from 19 to 93 which is 4200. It is divisible by 3 but not 9. For divisibility of higher power it has to be divisible by 9 but it is not divisible by 9. So higher power should be 1.

share|cite|improve this answer

answered Jul 28 at 13:07

Ninja hatori

105113

First of all calculate sum of digits that sum of natural numbers from 19 to 93 which is 4200. It is divisible by 3 but not 9. For divisibility of higher power it has to be divisible by 9 but it is not divisible by 9. So higher power should be 1.

share|cite|improve this answer

answered Jul 28 at 13:07

Ninja hatori

105113

share|cite|improve this answer

share|cite|improve this answer

answered Jul 28 at 13:07

Ninja hatori

105113

answered Jul 28 at 13:07

Ninja hatori

105113

answered Jul 28 at 13:07

Ninja hatori

105113

105113

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Brilliant! Wonder how it could be done if the sum were divisible by $9$
  – rsadhvika
  Jul 28 at 13:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @rsadhvika hint might help.
  – Ninja hatori
  Jul 28 at 13:41
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Brilliant! Wonder how it could be done if the sum were divisible by $9$
  – rsadhvika
  Jul 28 at 13:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @rsadhvika hint might help.
  – Ninja hatori
  Jul 28 at 13:41
  

  
  
  
  

Brilliant! Wonder how it could be done if the sum were divisible by $9$
– rsadhvika
Jul 28 at 13:26

Brilliant! Wonder how it could be done if the sum were divisible by $9$
– rsadhvika
Jul 28 at 13:26

@rsadhvika hint might help.
– Ninja hatori
Jul 28 at 13:41

@rsadhvika hint might help.
– Ninja hatori
Jul 28 at 13:41

add a comment |