Question en arithmétique

Marwane
Marwane
dans Arithmétique
Bonjour
Voici le problème que j'ai rencontré.

Supposons un entier N=pq, on connaît p et q, comment peut-on retrouver deux entiers r, s (s'ils existent) tel que :
N = 2*r*s + r + s
Merci bien de vouloir aider !
Marwane

Réponses

  • Dom
    Dom
    Si c’est possible, alors $N=(r+s)^2$.
    Est-ce toujours le cas ?

    N’importe quoi, pardon...
  • lourrran
    lourrran
    Si $ N=2rs+r+s$ alors $2N+1=(2r+1)(2s+1)$ Et donc, il suffit de trouver les diviseurs de 2N+1 pour conclure.
    Mais j'imagine que dans la réponse attendue, la décomposition N=pq devait servir à quelque chose.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • nicolas.patrois
    nicolas.patrois
    Avec un script bourrin : 
    n=139*271

r=1
while r<n:
	s,R=divmod(n-r,2*r+1)
	if R==0:
		print(s,r)
		assert n==2*r*s+r+s
	r+=1
    On obtient : 
    12556 1
4185 4
3424 5
1141 16
380 49
49 380
16 1141
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • gerard0
    gerard0
    Bonsoir Marwane.

    Sans condition particulière sur r et s, r=0 et s=N conviennent. Lorsque 2N+1 est premier (par exemple N=7*3 = 21), la seule valeur possible est r=0 ou s=0 (et l'autre égale à N). Conséquence du calcul de Iourran.

    D'où sort ton problème ?

    Cordialement
  • Marwane
    Marwane
    Merci beaucoup pour vos réponses.

    r et s sont non nuls, existe-t-il un algo rapide pour retrouver r et s s'ils existent ?


    Merci,

    Marwane
  • Fin de partie
    Fin de partie
    Gerard0:

    Probablement une tentative pour trouver un algo mirifique qui va factoriser un entier. Les paris sont ouverts. B-)
  • gerard0
    gerard0
    Gerard0 a écrit:
    D'où sort ton problème ?
    En particulier, on ne voit pas ce que n=pq vient faire dans l'histoire.
  • Tonm
    Tonm
    Peut être $r=-1$ et $s=-1-pq$.
    Mais je pense tu voulais $r$ et $s$ positifs en posant $r=s+h$, tu auras à trouver des entiers $h$ et $y$ tel que $(h+1)^2-2(h-pq)=y^2$. (c'est le $\Delta$ d'une équation du second degré en $s$)
    Cordialement.

    Ou $(h^2+1+2pq)=(h+k)^2$ et c'est $k(2k+1)=2pq+1$.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 1

1 Invité