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}$$
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.
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.
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?
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.....
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.
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.
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}$$