Dtjytyk

Curses work by shouting - How to avoid collateral damage?

What is the opposite of 'gravitas'?

Are there any comparative studies done between Ashtavakra Gita and Buddhim?

What are the ramifications of creating a homebrew world without an Astral Plane?

Is HostGator storing my password in plaintext?

Applicability of Single Responsibility Principle

Is this Spell Mimic feat balanced?

Increase performance creating Mandelbrot set in python

What defines a dissertation?

Is it correct to write "is not focus on"?

What would be the benefits of having both a state and local currencies?

Will it be accepted, if there is no ''Main Character" stereotype?

What will be the benefits of Brexit?

Was Spock the First Vulcan in Starfleet?

Can criminal fraud exist without damages?

Efficiently merge handle parallel feature branches in SFDX

Can I use my Chinese passport to enter China after I acquired another citizenship?

How does residential electricity work?

Products and sum of cubes in Fibonacci

What is the oldest known work of fiction?

The plural of 'stomach"

How does it work when somebody invests in my business?

What does this 7 mean above the f flat

Is expanding the research of a group into machine learning as a PhD student risky?

Can I find all solutions of $2^{n-1}equiv kmod n$?

Is there a solution for $2^{n-1}equiv 2^{16}+1mod n$ or $2^{n-1}equiv 2^{26}+1mod n$?Suppose $p$ is an odd prime. Show that $x^4 equiv-1$ (mod $p$) has a solution if and only if $p equiv1$ (mod $8$).How many solutions are there for $x^3 equiv -1mod(365)$?Show $a^2+b^2 equiv 0 mod p$ has no solutions except $a equiv b equiv 0 mod p Longleftrightarrow -1$ is a non-square modulo $p$.Number of solutions to $x^2equiv b mod p^n$On simple integer solutions of $2^{(yp-2)/(p-2)!}=px+1,$ where $p$ is a fixed prime $equiv 1text{ mod }4$Counting the number of solutions of the congruence $x^kequiv h$ (mod q)Prove: $k^2 equiv 1 mod p implies k equiv pm1 mod p$Is $p^2+q^2+r^2=3^k$ with primes $p,q,r$ solvable for every odd positive integer $kge 3 $?Show that if $m equiv 3 mod 4$, then $m$ has a prime factor $p equiv 3 mod 4$.If $t^p-(r^p+s^p) equiv 0 (mod p)$ implies $t-(r+s)=pq$, do other solutions exist for relatively prime $r$, $s$ and $t$?

2

2

$begingroup$

Suppose$ kge 2 $ is a positive integer.

Can I find all positive integers $ n>1 $ with $$2^{n-1}equiv kmod n$$ ?

I only found out yet that there is always a solution if $ k>2 $ and $ k-1 $ is not a power of $ 2 $. In this case, $ k $ has an odd prime factor $ q $, for which we have $ 2^{q-1}equiv kmod q $ as desired.

I am particularly interested whether for $ k=5 $, there is a solution and whether for $ k=11 $, there is a solution besides $ n=5 $. Finally, for $ k=3 $, is $ 10669 $ the only solution?

number-theory elementary-number-theory modular-arithmetic

share|cite|improve this question

edited Mar 15 at 8:57

YuiTo Cheng

2,1362837

asked Mar 15 at 8:53

PeterPeter

49.1k1240136

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  First thought : if $k-1$ is prime (and not equal to $2$), then by Fermat's little theorem, $n=k-1$ is a solution of your equation.
  $endgroup$
  – TheSilverDoe
  Mar 15 at 9:34
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's why I added that $k-1$ is not equal to $2$ :)
  $endgroup$
  – TheSilverDoe
  Mar 15 at 9:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes but with $n=k-1$, $1$ and $k$ are the same modulo $n$.
  $endgroup$
  – TheSilverDoe
  Mar 15 at 9:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok, I got it now, but this is what I worked out more generally. If $k-1$ has an odd prime factor, this prime factor is a solution.
  $endgroup$
  – Peter
  Mar 15 at 9:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @RoddyMacPhee Not quite, If I knew $n$ and would search $m$ with $2^mequiv kmod n$, you were right. But I search $n$
  $endgroup$
  – Peter
  Mar 15 at 13:24
  
  
  

  
  
  
  

 | 
show 5 more comments

2

2

$begingroup$

Suppose$ kge 2 $ is a positive integer.

Can I find all positive integers $ n>1 $ with $$2^{n-1}equiv kmod n$$ ?

I only found out yet that there is always a solution if $ k>2 $ and $ k-1 $ is not a power of $ 2 $. In this case, $ k $ has an odd prime factor $ q $, for which we have $ 2^{q-1}equiv kmod q $ as desired.

I am particularly interested whether for $ k=5 $, there is a solution and whether for $ k=11 $, there is a solution besides $ n=5 $. Finally, for $ k=3 $, is $ 10669 $ the only solution?

number-theory elementary-number-theory modular-arithmetic

share|cite|improve this question

edited Mar 15 at 8:57

YuiTo Cheng

2,1362837

asked Mar 15 at 8:53

PeterPeter

49.1k1240136

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  First thought : if $k-1$ is prime (and not equal to $2$), then by Fermat's little theorem, $n=k-1$ is a solution of your equation.
  $endgroup$
  – TheSilverDoe
  Mar 15 at 9:34
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That's why I added that $k-1$ is not equal to $2$ :)
  $endgroup$
  – TheSilverDoe
  Mar 15 at 9:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes but with $n=k-1$, $1$ and $k$ are the same modulo $n$.
  $endgroup$
  – TheSilverDoe
  Mar 15 at 9:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok, I got it now, but this is what I worked out more generally. If $k-1$ has an odd prime factor, this prime factor is a solution.
  $endgroup$
  – Peter
  Mar 15 at 9:42
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @RoddyMacPhee Not quite, If I knew $n$ and would search $m$ with $2^mequiv kmod n$, you were right. But I search $n$
  $endgroup$
  – Peter
  Mar 15 at 13:24
  
  
  

  
  
  
  

 | 
show 5 more comments

$begingroup$

Suppose$ kge 2 $ is a positive integer.

Can I find all positive integers $ n>1 $ with $$2^{n-1}equiv kmod n$$ ?

I only found out yet that there is always a solution if $ k>2 $ and $ k-1 $ is not a power of $ 2 $. In this case, $ k $ has an odd prime factor $ q $, for which we have $ 2^{q-1}equiv kmod q $ as desired.

I am particularly interested whether for $ k=5 $, there is a solution and whether for $ k=11 $, there is a solution besides $ n=5 $. Finally, for $ k=3 $, is $ 10669 $ the only solution?

number-theory elementary-number-theory modular-arithmetic

share|cite|improve this question

edited Mar 15 at 8:57

YuiTo Cheng

2,1362837

asked Mar 15 at 8:53

PeterPeter

49.1k1240136

$endgroup$

share|cite|improve this question

edited Mar 15 at 8:57

YuiTo Cheng

2,1362837

asked Mar 15 at 8:53

PeterPeter

49.1k1240136

share|cite|improve this question

edited Mar 15 at 8:57

YuiTo Cheng

2,1362837

asked Mar 15 at 8:53

PeterPeter

49.1k1240136

edited Mar 15 at 8:57

YuiTo Cheng

2,1362837

edited Mar 15 at 8:57

YuiTo Cheng

2,1362837

asked Mar 15 at 8:53

PeterPeter

49.1k1240136

asked Mar 15 at 8:53

PeterPeter

49.1k1240136

2 Answers
2

active

oldest

votes

0

$begingroup$

Clearly n can not be prime. I had following experiment:

$2^{4-1}=8=2times 4 +0$

$2^{6-1}=32=5times 6 +2$

$2^{8-1}=128=16times 8+0$

$2^{9-1}=256=28times 9 +4$

$2^{10-1}=512=51times 10+2$

$2^{12-1}=2042=170times 12 +8$

$2^{14-1}=8192=585times 14 +2$

$2^{15-1}=16384=1092times 15 +4$

$2^{16-1}=32768=2048times 16 +0$

$2^{17-1}=65536=3855times 17 +1$

$2^{18-1}=131072=7281times 18+14$

$2^{33-1} ≡4 mod 33$

$2^{27-1} ≡13 mod 27$

A: if $n=2^t$ then $k=0$

B: if $n-1=2^t$ and $t=2s$ then $k=1$

C: if $n-1=2^t$ and $t=2s+1$ then $k=2^u$

D: Else $k=2^v$ or $k=k_1$; $k_1∈N$

share|cite|improve this answer

edited Mar 18 at 16:44

answered Mar 16 at 2:12

siroussirous

1,7051514

$endgroup$

add a comment | 

-1

$begingroup$

Here is what I meant by my comments ( not a full answer):$$2^{n-1}equiv k bmod nimplies begin{cases}2^{n-1}equiv k bmod 2nqquad,kequiv 0bmod 2\2^{n-1}equiv k+n bmod 2nqquad,k+nequiv 0bmod 2end{cases} $$ or $n-1$ is the discrete log of k mod n. The second case means, if k is odd, n is odd. Otherwise, distributivity fails when turned into linear polynomials equalities. You can use mod 3n to work k and n mod 3 ( 3 cases, 6 once you consider the two possibilities mod 3 for a power of 2) etc. In general though, $n-1$ needs be a multiple/on the same arithmetic progression of/as the discrete log in most cases though, so it falls to the discrete log problem.

share|cite|improve this answer

edited Mar 15 at 13:53

answered Mar 15 at 13:39

Roddy MacPheeRoddy MacPhee

517118

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3149076%2fcan-i-find-all-solutions-of-2n-1-equiv-k-mod-n%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

Clearly n can not be prime. I had following experiment:

$2^{4-1}=8=2times 4 +0$

$2^{6-1}=32=5times 6 +2$

$2^{8-1}=128=16times 8+0$

$2^{9-1}=256=28times 9 +4$

$2^{10-1}=512=51times 10+2$

$2^{12-1}=2042=170times 12 +8$

$2^{14-1}=8192=585times 14 +2$

$2^{15-1}=16384=1092times 15 +4$

$2^{16-1}=32768=2048times 16 +0$

$2^{17-1}=65536=3855times 17 +1$

$2^{18-1}=131072=7281times 18+14$

$2^{33-1} ≡4 mod 33$

$2^{27-1} ≡13 mod 27$

A: if $n=2^t$ then $k=0$

B: if $n-1=2^t$ and $t=2s$ then $k=1$

C: if $n-1=2^t$ and $t=2s+1$ then $k=2^u$

D: Else $k=2^v$ or $k=k_1$; $k_1∈N$

share|cite|improve this answer

edited Mar 18 at 16:44

answered Mar 16 at 2:12

siroussirous

1,7051514

$endgroup$

add a comment | 

0

$begingroup$

Clearly n can not be prime. I had following experiment:

$2^{4-1}=8=2times 4 +0$

$2^{6-1}=32=5times 6 +2$

$2^{8-1}=128=16times 8+0$

$2^{9-1}=256=28times 9 +4$

$2^{10-1}=512=51times 10+2$

$2^{12-1}=2042=170times 12 +8$

$2^{14-1}=8192=585times 14 +2$

$2^{15-1}=16384=1092times 15 +4$

$2^{16-1}=32768=2048times 16 +0$

$2^{17-1}=65536=3855times 17 +1$

$2^{18-1}=131072=7281times 18+14$

$2^{33-1} ≡4 mod 33$

$2^{27-1} ≡13 mod 27$

A: if $n=2^t$ then $k=0$

B: if $n-1=2^t$ and $t=2s$ then $k=1$

C: if $n-1=2^t$ and $t=2s+1$ then $k=2^u$

D: Else $k=2^v$ or $k=k_1$; $k_1∈N$

share|cite|improve this answer

edited Mar 18 at 16:44

answered Mar 16 at 2:12

siroussirous

1,7051514

$endgroup$

add a comment | 

$begingroup$

Clearly n can not be prime. I had following experiment:

$2^{4-1}=8=2times 4 +0$

$2^{6-1}=32=5times 6 +2$

$2^{8-1}=128=16times 8+0$

$2^{9-1}=256=28times 9 +4$

$2^{10-1}=512=51times 10+2$

$2^{12-1}=2042=170times 12 +8$

$2^{14-1}=8192=585times 14 +2$

$2^{15-1}=16384=1092times 15 +4$

$2^{16-1}=32768=2048times 16 +0$

$2^{17-1}=65536=3855times 17 +1$

$2^{18-1}=131072=7281times 18+14$

$2^{33-1} ≡4 mod 33$

$2^{27-1} ≡13 mod 27$

A: if $n=2^t$ then $k=0$

B: if $n-1=2^t$ and $t=2s$ then $k=1$

C: if $n-1=2^t$ and $t=2s+1$ then $k=2^u$

D: Else $k=2^v$ or $k=k_1$; $k_1∈N$

share|cite|improve this answer

edited Mar 18 at 16:44

answered Mar 16 at 2:12

siroussirous

1,7051514

$endgroup$

share|cite|improve this answer

edited Mar 18 at 16:44

answered Mar 16 at 2:12

siroussirous

1,7051514

answered Mar 16 at 2:12

siroussirous

1,7051514

answered Mar 16 at 2:12

siroussirous

1,7051514

-1

$begingroup$

Here is what I meant by my comments ( not a full answer):$$2^{n-1}equiv k bmod nimplies begin{cases}2^{n-1}equiv k bmod 2nqquad,kequiv 0bmod 2\2^{n-1}equiv k+n bmod 2nqquad,k+nequiv 0bmod 2end{cases} $$ or $n-1$ is the discrete log of k mod n. The second case means, if k is odd, n is odd. Otherwise, distributivity fails when turned into linear polynomials equalities. You can use mod 3n to work k and n mod 3 ( 3 cases, 6 once you consider the two possibilities mod 3 for a power of 2) etc. In general though, $n-1$ needs be a multiple/on the same arithmetic progression of/as the discrete log in most cases though, so it falls to the discrete log problem.

share|cite|improve this answer

edited Mar 15 at 13:53

answered Mar 15 at 13:39

Roddy MacPheeRoddy MacPhee

517118

$endgroup$

add a comment | 

-1

$begingroup$

Here is what I meant by my comments ( not a full answer):$$2^{n-1}equiv k bmod nimplies begin{cases}2^{n-1}equiv k bmod 2nqquad,kequiv 0bmod 2\2^{n-1}equiv k+n bmod 2nqquad,k+nequiv 0bmod 2end{cases} $$ or $n-1$ is the discrete log of k mod n. The second case means, if k is odd, n is odd. Otherwise, distributivity fails when turned into linear polynomials equalities. You can use mod 3n to work k and n mod 3 ( 3 cases, 6 once you consider the two possibilities mod 3 for a power of 2) etc. In general though, $n-1$ needs be a multiple/on the same arithmetic progression of/as the discrete log in most cases though, so it falls to the discrete log problem.

share|cite|improve this answer

edited Mar 15 at 13:53

answered Mar 15 at 13:39

Roddy MacPheeRoddy MacPhee

517118

$endgroup$

add a comment | 

$begingroup$

Here is what I meant by my comments ( not a full answer):$$2^{n-1}equiv k bmod nimplies begin{cases}2^{n-1}equiv k bmod 2nqquad,kequiv 0bmod 2\2^{n-1}equiv k+n bmod 2nqquad,k+nequiv 0bmod 2end{cases} $$ or $n-1$ is the discrete log of k mod n. The second case means, if k is odd, n is odd. Otherwise, distributivity fails when turned into linear polynomials equalities. You can use mod 3n to work k and n mod 3 ( 3 cases, 6 once you consider the two possibilities mod 3 for a power of 2) etc. In general though, $n-1$ needs be a multiple/on the same arithmetic progression of/as the discrete log in most cases though, so it falls to the discrete log problem.

share|cite|improve this answer

edited Mar 15 at 13:53

answered Mar 15 at 13:39

Roddy MacPheeRoddy MacPhee

517118

$endgroup$

share|cite|improve this answer

edited Mar 15 at 13:53

answered Mar 15 at 13:39

Roddy MacPheeRoddy MacPhee

517118

answered Mar 15 at 13:39

Roddy MacPheeRoddy MacPhee

517118

answered Mar 15 at 13:39

Roddy MacPheeRoddy MacPhee

517118