43^p mod 247=17

Here's a method that works 'on paper', no calculator needed.

\(43^{p}(\text{mod}247)=17\) means that \(43^{p}\) when divided by 247, leaves a remainder of 17.

That means that for some k, \(43^{p}-247k=17\), or, equivalently, \(43^{p}-17=247k.\)

Since 247 = 13*19, it follows that \(43^{p}-17\) has to be divisible by both 13 and 19.

Working with mod 13,

\(43\equiv4,\:43^{2}\equiv3,\:43^{3}\equiv-1, \:43^{4}\equiv-4,\text{ etc.}\)

The sequence is easy to work out, the last one, for example, can be worked out using the earlier figures,

\(43^{4}=43^{2}.43^{2}\equiv3\times3=9\equiv-4,\)

or,

\(43^{4}=43.43^{3}\equiv 4\times(-1)=-4\equiv-4.\)

The result is interpreted as the remainder when 43^4 is divided by 13 is 9 (or it overshoots by 4).

(43^4 = 3418801 = 262984*13 + 9, or 43^4 = 3418801 = 262985*13 - 4).

Since \(17\equiv4,\) the sequence for \(43^{p}-17\) begins 0, -1, -5, -8, , ... and what we are looking for are zero entries, (which means that there will be a remainder of zero when dividing by 13).

The first zero (coming from 4 - 4) is saying that 43 - 17 = 26 is divisible by 13.

Running the sequence further produces

0, -1, -5, -8, -7, -3, 0, -1, -5, -8, -7, -3, 0, -1, -5, ...

so we have zeros for p = 1, 7, 13, and at intervals of six thereafter.

Now working with mod 19 to determine when 43^p - 17 is divisible by 19, produces the sequence (noting that \(17\equiv-2(\text{mod}19)\)),

7, 8, -6, 0, 11, 9, -1, 6, 3, 7, 8, -6, 0, 11, ...

so we have zeros for p = 4, 13 and at intervals of nine thereafter.

Putting the two p sequences side by side we have

1, 7, 13, 19, 25, 31, 37, ...

and

4, 13, 22, 31, 40, ....

so we have matching zeros (divisibility by both 13 and 19) at p = 13, 31, ...

p = 13

More generally when p = 18n + 13  where n = 0, 1, 2, ... etc.

Could you explain please Alan ?

There are an infinite number of values of p for which 43^p mod 247 is 17.  Here are a few:

Thanks Alan, I have been looking at your solution.

I can see that you have given me the answers and shown that they are correct but I don't think you have shown me how to do it.

Did you just use iterations on your mathlab program to rule numbers in or out.?

I tried to do it like this  in excel but I don't think that the excel precision is good enough.

Anyway I was hoping for a more mathematical solution.   :(

Thanks Guest,

I have put this question back on my watchlist.  I shall have a good look at you answer when I get a chance. 

Hi Guest,  I looked through your answer today and was most impressed.

It made perfect sense - thanks for that.

It would have been good if you had identified yourself - you could give yourself a name even if you don't want to become a member or if you cannot sign in.

Our only member who you may be is Bertie.  Did you answer this for me Bertie?

-------------------------------------------------

A general comment and question.

 I only started learning modular arithmetic from this forum so I have never formally learned the rules.

This seems to be one of the main ones.

\(\boxed{ mod\;b\;(t*q)=mod\;b\;[mod\;b\;(t)*mod\;b\;(q) ] }\)

This seems to be reasonable but I would  be interested in seeing a proof.

What are the other 'rules'

I suppose there is lots of information on this on other sites.  I am being lazy.

I want the short answer, not the long one.  LOL

Hi Melody, yes guilty, that's one of my answers - Bertie.

You ask about modular arithmetic.

The basic rules are pretty simple and are easy to prove using some simple algebra.

Two integers x and y are said to be congruent modulo n, written

\(\qquad x\equiv y (\text{mod } n)\)

if they each give the same remainder ( less than n) when they are divided by n.

That is, if the remainder is r, (equal to or greater than zero, but less than n), then

\(x = k_{1}n + r\)

and

\(y = k_{2}n + r\)

for some integers \(k_{1} \text{ and }k_{2}. \)

Subtracting one from the other gets us \(x - y = (k_{1}-k_{2})n = kn,\) for some integer k.

So, often more convenient in practice, x - y is a multiple of n.

The basic rules are then, if   \(x\equiv y(\text{mod }n) \text{ and } u\equiv v(\text{mod }n),\)

then

\(x + u \equiv y + v(\text{mod }n)\)

(just one (mod n) at the end of the line is normal practice)

and

\(x\times u\equiv y\times v(\text{mod }n)\).

They are both easy to prove if you write them out in the equation form used earlier.

(  x - y = k(1)n, u - v = k(2)n, adding, (x + u) - (y + v) = (k(1) + k(2))n = kn, etc., multiply the two equations to prove the multiplcation result.)

As an example/confirmation of the two rules, given that  \(N = (22\times 31) + (11\times 17) + (13\times 19)\),

calculate the remainder when N is divided by 7.

Working to modulo 7,

\((22\times 31)+(11\times 17)+(13\times 19)\equiv (1\times3)+(4\times 3)+(6\times 5)\equiv45\equiv 3.\)

Check, N = 1116 = 159*7 + 3.

Division is a bit more awkward, since the division of one integer by another need not be an integer. Subtraction is ok though.

Thanks you Bertie,

We have to get you back on this forum properly!  I nearly missed your post!

I will take a really good look at what you have said and tuck your post away in a safe spor that i can find later. :)

If you are in the mood it would be good if you post a modular question every now and again so that I, and maybe others, can practice.  

For some reason modular arithmetic and diophantine equations have caught my imagination for the moment.  Probably because they do not seem that difficult but I have only had very recent experience with them.

Anyway, thanks, much appreciated :))