+0  
 
0
2146
9
avatar

show that 7^p-6^p-1 for p > 3 prime is multiple of 43

difficulty advanced
 Jun 7, 2015

Best Answer 

 #8
avatar+26393 
+10

show that 7^p-6^p-1 for p > 3 prime is multiple of 43

 

$$\boxed{~~\textcolor[rgb]{0,150,0}{7} ^p - \textcolor[rgb]{0,0,150}{6}^p -1 \equiv 0 \mod 43 ~~, \quad \mathrm{if~~} p \mathrm{~~is~prime~and~~} p > 3.
} \\\\
\begin{array}{lrclcl}
\mathrm{Because~~ } &\textcolor[rgb]{0,150,0}{7}^6 &=& 117649 &\equiv& \textcolor[rgb]{1,0,0}{1} \mod 43\\
\mathrm{~~and~~ }\\
&\textcolor[rgb]{0,0,150}{6}^6 &=& 46656 &\equiv& \textcolor[rgb]{1,0,0}{1} \mod 43\\
\mathrm{~~and~~ }\\
&43 &=& \textcolor[rgb]{0,0,150}{6}\cdot \textcolor[rgb]{0,150,0}{7} + 1\\
\mathrm{~~and~~ }\\
&\textcolor[rgb]{0,0,150}{6} &=& \textcolor[rgb]{0,150,0}{7} - 1
\end{array}$$

 

If it can be this case generally is valid ?

$$\boxed{~~\textcolor[rgb]{0,150,0}{a} ^p - \textcolor[rgb]{0,0,150}{(a-1)}^p -1 \equiv 0 \mod [\textcolor[rgb]{0,150,0}{a} \textcolor[rgb]{0,0,150}{(a-1)} +1] ~~, \quad \mathrm{if~~} p \mathrm{~~is~prime~and~~} p > 3.
} \\\\
\begin{array}{lrclcl}
\mathrm{Because~~ } &\textcolor[rgb]{0,150,0}{a}^6 &&&\equiv& \textcolor[rgb]{1,0,0}{1} \mod [\textcolor[rgb]{0,150,0}{a} \textcolor[rgb]{0,0,150}{(a-1)} +1]\\
\mathrm{~~and~~ }\\
&\textcolor[rgb]{0,0,150}{(a-1)}^6 &&&\equiv& \textcolor[rgb]{1,0,0}{1} \mod [\textcolor[rgb]{0,150,0}{a} \textcolor[rgb]{0,0,150}{(a-1)} +1]\\
\end{array}$$

 

Examples:

$$\begin{array}{|c|c|l|l|c|}
\hline
\textcolor[rgb]{0,150,0}{a}
& \textcolor[rgb]{0,0,150}{a-1}
&\mathrm{~~multiple ~of~~ }&&\\
\hline
2 & 1 & 2*1+1 = 3 & 2^6 = 64 \equiv 1 \mod 3 & 2^p - 1^p - 1 \equiv 0 \mod 3 \\
& & & 1^6 = 1 \equiv 1 \mod 3 &\\
\hline
3 & 2 & 3*2+1 = 7 & 3^6 = 729 \equiv 1 \mod 7 & 3^p - 2^p - 1 \equiv 0 \mod 7 \\
& & & 2^6 = 64 \equiv 1 \mod 7 &\\
\hline
4 & 3 & 4*3+1 = 13 & 4^6 = 4096 \equiv 1 \mod 13 & 4^p - 3^p - 1 \equiv 0 \mod 13 \\
& & & 3^6 = 729 \equiv 1 \mod 13& \\
\hline
5 & 4 & 5*4+1 = 21 & 5^6 = 15625 \equiv 1 \mod 21 & 5^p - 4^p - 1 \equiv 0 \mod 21 \\
& & & 4^6 = 4096 \equiv 1 \mod 21& \\
\hline
6 & 5 & 6*5+1 = 31 & 6^6 = 46656 \equiv 1 \mod 31 & 6^p - 5^p - 1 \equiv 0 \mod 31 \\
& & & 5^6 = 15625 \equiv 1 \mod 31& \\
\hline
7 & 6 & 7*6+1 = 43 & 7^6 = 117649 \equiv 1 \mod 43 & \textcolor[rgb]{1,0,0}{ 7^p - 6^p - 1 \equiv 0 \mod 43 } \\
& & & 6^6 = 46656 \equiv 1 \mod 43 &\\
\hline
8 & 7 & 8*7+1 = 57 & 8^6 = 262144 \equiv 1 \mod 57 & 8^p - 7^p - 1 \equiv 0 \mod 57 \\
& & & 7^6 = 117649 \equiv 1 \mod 57 &\\
\hline
\cdots & \cdots & & & \cdots\\
\hline
\end{array}$$

 

 Jun 12, 2015
 #1
avatar+893 
+10

All primes greater than 3 can be expressed in the form 6n+1 or 6n-1.

For example, 5 = 6 - 1,

7 = 6 + 1,

11 = 2.6 - 1,

13 = 2.6 + 1,

17 = 3.6 - 1

19 = 3.6 + 1,

23 = 4.6 - 1,

and so on.

There are a whole load of numbers for which 6n plus or minus 1 is not prime, but the important point is that 6n plus or minus one covers all of the primes greater than 3. 

 

Consider then

$$N = 7^{\, 6n+1}-6^{\,6n+1}-1=(7\times7^{\,6n})-(6\times6^{\,6n})-1.$$

 

Now

$$7^{\,6}=117649=2736\times 43 + 1\equiv1(\bmod 43),$$

so

$$(7^{\,6})^{2}, (7^{\,6})^{3},\:\text{and in general}\:(7^{\,6})^{n}=7^{\,6n}\equiv 1(\bmod 43),$$

in which case

$$7\times7^{\,6n}\equiv7\times 1\equiv7(\bmod 43).$$

 

Similarly, since

$$6^{\,6}=46656=1085\times 43 + 1\equiv1(\bmod 43),$$

$$6\times6^{\,6n}\equiv 6(\bmod43).$$

 

It follows that

$$N\equiv7-6-1\equiv 0(\bmod 43),$$

that is , there is a remainder of zero if N is divided by 43.

 

To cover the 6n - 1 case, consider

$$42N =7\times 6(7^{\,6n-1}-6^{\,6n-1}-1)=(6\times7^{\,6n})-(7\times6^{\,6n})-42.$$

Proceeding as above,

$$42N\equiv6-7+1\equiv0(\bmod43),$$

implying that 42N is divisible by 43, and since 42 isn't, it follows that N is.

 Jun 9, 2015
 #2
avatar+118673 
0

Thanks Bertie,   I am always so pleased when you show yourself on our forum.  

 

And, as expected, your answer looks amazing.  :))

 

Another for me to study and hopefully absorb.   

 Jun 10, 2015
 #3
avatar+118673 
0

WOW

 

There are a whole load of numbers for which 6n plus or minus 1 is not prime, but the important point is that

6n plus or minus one covers all of the primes greater than 3. 

 

I never knew that.  Is that one of those things that plebs like me just have to accept, or is there an understandable proof floating around out there in the ether?     

 Jun 10, 2015
 #4
avatar+129852 
+10

Here's a "proof,"  Melody........consider  the number line......

 

..6n - 6   6n - 5    6n - 4   6n - 3    6n - 2    6n - 1    6n     6n+1    6n + 2   6n+3   6n+ 4    6n + 5    6n + 6..

 

Note that  the terms  6n-6, 6n + 6, 6n - 4, 6n+ 4, 6n - 3, 6n + 3, 6n - 2, 6n + 2 and 6n  cannot be primes

 

The only possible  primes are 6n - 5, 6n -1 , 6n + 1 , 6n + 5.......but note that, 6n - 5 is really just the same thing  as 6(n -1) + 1   and 6n + 5 is the same thing as 6(n + 1) - 1.....in other words, the only possible primes on the number line occur on either side of a integer which is divisible by 6, i.e., 6n - 1 or 6n + 1.......

 

And as Bertie points out, we have to make an exception for 2 and 3.....

 

 

 Jun 10, 2015
 #5
avatar+118673 
+5

Thanks Chris,  that is really neat!

I think I understand what Bertie has done as well.  I must be on a roll.    

 

I think I should go looking for some introductory videos on modular arithemetic.

The basic stuff is not that hard but it is not cemented in my brain very well yet.  

 

Anyway I will store this thread in our "reference material" sticky thread.  

 Jun 10, 2015
 #6
avatar+893 
+5

Thanks for the comments Melody.

Notice that the 6n plus or minus 1 thing is not unique, 2n or 4n plus or minus 1 share the same property.

I chose 6n because the 6 happened to fit in with the question.

 Jun 11, 2015
 #7
avatar+118673 
0

Thanks Bertie,

I think i can see that.  I shall think on it :/

 Jun 11, 2015
 #8
avatar+26393 
+10
Best Answer

show that 7^p-6^p-1 for p > 3 prime is multiple of 43

 

$$\boxed{~~\textcolor[rgb]{0,150,0}{7} ^p - \textcolor[rgb]{0,0,150}{6}^p -1 \equiv 0 \mod 43 ~~, \quad \mathrm{if~~} p \mathrm{~~is~prime~and~~} p > 3.
} \\\\
\begin{array}{lrclcl}
\mathrm{Because~~ } &\textcolor[rgb]{0,150,0}{7}^6 &=& 117649 &\equiv& \textcolor[rgb]{1,0,0}{1} \mod 43\\
\mathrm{~~and~~ }\\
&\textcolor[rgb]{0,0,150}{6}^6 &=& 46656 &\equiv& \textcolor[rgb]{1,0,0}{1} \mod 43\\
\mathrm{~~and~~ }\\
&43 &=& \textcolor[rgb]{0,0,150}{6}\cdot \textcolor[rgb]{0,150,0}{7} + 1\\
\mathrm{~~and~~ }\\
&\textcolor[rgb]{0,0,150}{6} &=& \textcolor[rgb]{0,150,0}{7} - 1
\end{array}$$

 

If it can be this case generally is valid ?

$$\boxed{~~\textcolor[rgb]{0,150,0}{a} ^p - \textcolor[rgb]{0,0,150}{(a-1)}^p -1 \equiv 0 \mod [\textcolor[rgb]{0,150,0}{a} \textcolor[rgb]{0,0,150}{(a-1)} +1] ~~, \quad \mathrm{if~~} p \mathrm{~~is~prime~and~~} p > 3.
} \\\\
\begin{array}{lrclcl}
\mathrm{Because~~ } &\textcolor[rgb]{0,150,0}{a}^6 &&&\equiv& \textcolor[rgb]{1,0,0}{1} \mod [\textcolor[rgb]{0,150,0}{a} \textcolor[rgb]{0,0,150}{(a-1)} +1]\\
\mathrm{~~and~~ }\\
&\textcolor[rgb]{0,0,150}{(a-1)}^6 &&&\equiv& \textcolor[rgb]{1,0,0}{1} \mod [\textcolor[rgb]{0,150,0}{a} \textcolor[rgb]{0,0,150}{(a-1)} +1]\\
\end{array}$$

 

Examples:

$$\begin{array}{|c|c|l|l|c|}
\hline
\textcolor[rgb]{0,150,0}{a}
& \textcolor[rgb]{0,0,150}{a-1}
&\mathrm{~~multiple ~of~~ }&&\\
\hline
2 & 1 & 2*1+1 = 3 & 2^6 = 64 \equiv 1 \mod 3 & 2^p - 1^p - 1 \equiv 0 \mod 3 \\
& & & 1^6 = 1 \equiv 1 \mod 3 &\\
\hline
3 & 2 & 3*2+1 = 7 & 3^6 = 729 \equiv 1 \mod 7 & 3^p - 2^p - 1 \equiv 0 \mod 7 \\
& & & 2^6 = 64 \equiv 1 \mod 7 &\\
\hline
4 & 3 & 4*3+1 = 13 & 4^6 = 4096 \equiv 1 \mod 13 & 4^p - 3^p - 1 \equiv 0 \mod 13 \\
& & & 3^6 = 729 \equiv 1 \mod 13& \\
\hline
5 & 4 & 5*4+1 = 21 & 5^6 = 15625 \equiv 1 \mod 21 & 5^p - 4^p - 1 \equiv 0 \mod 21 \\
& & & 4^6 = 4096 \equiv 1 \mod 21& \\
\hline
6 & 5 & 6*5+1 = 31 & 6^6 = 46656 \equiv 1 \mod 31 & 6^p - 5^p - 1 \equiv 0 \mod 31 \\
& & & 5^6 = 15625 \equiv 1 \mod 31& \\
\hline
7 & 6 & 7*6+1 = 43 & 7^6 = 117649 \equiv 1 \mod 43 & \textcolor[rgb]{1,0,0}{ 7^p - 6^p - 1 \equiv 0 \mod 43 } \\
& & & 6^6 = 46656 \equiv 1 \mod 43 &\\
\hline
8 & 7 & 8*7+1 = 57 & 8^6 = 262144 \equiv 1 \mod 57 & 8^p - 7^p - 1 \equiv 0 \mod 57 \\
& & & 7^6 = 117649 \equiv 1 \mod 57 &\\
\hline
\cdots & \cdots & & & \cdots\\
\hline
\end{array}$$

 

heureka Jun 12, 2015
 #9
avatar+118673 
0

Thanks Heureka  

 

This has been included in our reference material thread :)

 Jun 12, 2015

2 Online Users