Approche probabiliste d'une forme de factorisation ! (g peur !)

par **anismemo2003** » 23 Juin 2007, 21:48

Bon voila, j'espere que j'expliquerai bien.

on a :

y(k) = (1+( (4k-1) * n)) / 4 avec n = 4p +1 (entier naturel n)

on veut factoriser y(k) en y^2 = p * q
avec p == -k [4k - 1 ]

Je note Pn la proba que y(k) ne se factorise pas comme voulu pour k de 1 à n

pour k = 1
y ne se factorise pas comme suit : p == 2 [3]
ce qui represente 1 cas / 3 (factorisation possible)
donc son barre 2 cas / 3 (factorisation impossible)

pour k = 2
y ne se factorise pas comme suit : p == 5 [7]
ce qui represente 1 cas / 7 (factorisation possible)
donc son barre 6 cas / 7 (factorisation impossible)

pour k = 3
y ne se factorise pas comme suit : p == 8 [11]
ce qui represente 1 cas / 11 (factorisation possible)
donc son barre 10 cas / 11 (factorisation impossible)

et ainsi de suite

donc Pn = 2/3 * 6/7 * 10/11 * ( (4k-2) / (4k-1))

Ma question: est-ce que si je demontre que Pn tend vers 0 (qui est le cas), je peux en conclure qu'une telle factorisation est impossible en +infini ????

par **alben** » 23 Juin 2007, 22:54

anismemo2003 a écrit:y(k) = (1+( (4k-1) * n)) / 4 avec n = 4p +1 (entier naturel n)
on veut factoriser y(k) en y = p * q
avec p == -k [4k - 1 ]

Avant même d'essayer de comprendre, je voudrais être certain que les k et les p qui apparaissent sont bien les mêmes.
Est-ce que p est premier ?

par **anismemo2003** » 23 Juin 2007, 23:02

voila g mis n=4p'+1, ca c'est juste pour la forme de n pour avoir y entier

ni p ni q est premier, c'est juste des diviseurs de y

et oui le k c le meme...

Alors ?

par **alben** » 23 Juin 2007, 23:36

anismemo2003 a écrit:B
pour k = 1
y ne se factorise pas comme suit : p == 2 [3]
ce qui represente 1 cas / 3 (factorisation possible)
donc son barre 2 cas / 3 (factorisation impossible)

Merci, je continue donc la lecture.
Pour k=1 il faudra que p=2 modulo 3 et pq=y=3p'+1
pour p'=1, on a y=4 et p=2, q=2 ça marche
pour p'=2, on a y=7 et p=7, q=1 ça ne marche pas
pour p'=3, on a y=10 et p=5, q=2 ça marche
pour p'=4, on a y=13 et p=13, q=1 ça ne marche pas
pour p'=5, on a y=16 et p=8, q=2 ça marche
etc.. Je ne comprends pas pourquoi tu te limites à 3 cas

par **anismemo2003** » 23 Juin 2007, 23:50

nan la c une genre d'iteration, l'important c pas ces 3 cas, mais quand k varit de 1 a l'infinie, on est sur qu'une fois ca va marcher.
Au moins une fois. Tu vois la demarche ?

par **anismemo2003** » 23 Juin 2007, 23:50

attention y est généré a partir de n et k (n etant fixe : parametre).
tu dois inverser, du genre p'=2 on a :
k= ...

par **alben** » 24 Juin 2007, 00:00

anismemo2003 a écrit:nan la c une genre d'iteration, l'important c pas ces 3 cas, mais quand k varit de 1 a l'infinie, on est sur qu'une fois ca va marcher.
Au moins une fois. Tu vois la demarche ?

Désolé, je ne comprends plus rien...

par **anismemo2003** » 24 Juin 2007, 00:04

bon tu prend n=5 : il ya k=1 qui verifie la condition
apres tu prend n = 9 , il y aura k qui verifie la condition

donc quelque soit n, il y aura tjs un k qui verifie la condition.

Bon demontrer ca, g mis que la condition pour n fixé ne marche pas pour k=1, pour k=2 k=3 ... k=n ... k=(infini) et on remarque que plus k est grand plus la factorisation est de plus en plus possible!

je veux savoir si un tel raisonnement est juste : avoir demontré avec le proba un tel resultat le rend-t-il valable ?

merci pour ta patience ;) :)

par **emdro** » 24 Juin 2007, 10:26

anismemo2003 a écrit:
Ma question: est-ce que si je demontre que Pn tend vers 0 (qui est le cas), je peux en conclure qu'une telle factorisation est impossible en +infini ????

Bonjour, tu veux dire qu'une telle factorisation est possible?

Il faut faire attention aux probablilités dès que l'univers est infini:
* lorsque l'univers est fini, P(A)=0 A={} A est l'événement impossible;

Si l'univers est infini, ce n'est plus vrai.
exemple: je te demande de choisir un nombre entier au hasard. L'univers est donc IN. La probabilité que tu tombes sur 1023 par exemple est rigoureusement nulle, comme d'ailleurs celle de tomber sur n'importe quel entier. Cela ne signifie pas que ce soit impossible.
C'est d'ailleurs le sens du mot presque en maths: on dira qu'un événement est presque certain si sa probabilité vaut 1.

Dans ton cas, sachant que ton raisonnement porte sur une infinité de k possibles, tu pourras affirmer au mieux que la factorisation est presque certainement possible. Ce qui n'est "probablement" pas ce qu'on te demande!

par **emdro** » 24 Juin 2007, 10:52

anismemo2003 a écrit:apres tu prend n = 9 , il y aura k qui verifie la condition

Justement, pour n=9, tu parles d'un k qui vérifie la condition. Est-ce par exemple
k=2 car -2 qui est congru à -2 modulo 7 divise 16?

Je veux dire, acceptes-tu les diviseurs négatifs?

par **alben** » 24 Juin 2007, 11:16

Bonjour;
Bravo emdro, il semble que tu ais compris la question :++:
Je continue à essayer de lire le problème.
En fait on se donne p' et la question est de savoir si l'on peut trouver un k<4p'+2 qui permette la factorisation.
y=(4k-1)p'+k et l'un des facteurs doit être égal à -k modulo 4k-1
Si p'=1 k=1 marche
Si p'=2 aucun k inférieur à 10 ne marche
PS je viens de voir ton dernier message je crois bien qu'il impose k compris entre 1 et n (bornes incluses)

par **emdro** » 24 Juin 2007, 11:56

alben a écrit:Si p'=2 aucun k inférieur à 10 ne marche
PS je viens de voir ton dernier message je crois bien qu'il impose k compris entre 1 et n (bornes incluses)

Hello Alben,

Si p'=2, n=9.

Si tu prends k=2 (qui est bien entre 1 et 9), on obtient une possibilité en écrivant que 16=(-2)*(-8) et le diviseur -2 est bien congru à -k modulo 4k-1.

Ne confonds pas le k (qui doit être entre 1 et 9) et le diviseur éventuel p.
Si p doit être positif, il n'y a pas de solution; sinon, c'est possible.

par **emdro** » 24 Juin 2007, 12:10

Anismemo,

Il est facile de démontrer directement que N=(4k-1)p'+k admet un diviseur p congru à -k modulo (4k-1).

En effet il suffit de prendre p=-k+(4k-1)u avec u=-p'.
On obtient p=-k+(4k-1)(-p')
p=-[k+(4k-1)p']
p=-N

donc p divise bien N. L'inconvénient est qu'il est négatif. L'avantage est que cela ne dépend pas de k: cela marche tout le temps, en particulier pour k entre 1 et n.

Si tu exiges d'avoir un diviseur positif, ce n'est plus toujours possible. Prends p'=2 par exemple, et tu n'obtiendras pas de solution.

par **alben** » 24 Juin 2007, 16:44

Bravo emdro !
Tu as résolu la question sous réserve que ce soit bien la question :zen:

par **emdro** » 24 Juin 2007, 17:02

Alben,

Je ne suis pas très sûr non plus; je fais comme Elkabach et George Marchais: il vient avec ses questions, et moi avec mes réponses! :ptdr:

par **anismemo2003** » 24 Juin 2007, 19:12

remarque, les diviseur comme le gamma doit etre positifs

par **anismemo2003** » 24 Juin 2007, 19:15

remarque c gamma^2 qui doit etre factorisé de la sorte, non gamma. mais je suis partant que tu me demontre que n=9 ne marche pas :)

desolé :briques: je vais la corriger

par **alben** » 25 Juin 2007, 00:10

C'est quoi le gamma ? il n'y avait pas de gamma avant

par **anismemo2003** » 29 Juin 2007, 03:54

le gamma c le y

Approche probabiliste d'une forme de factorisation ! (g peur !)

Approche probabiliste d'une forme de factorisation ! (g peur !)

Qui est en ligne