Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Concept

Nombres premiers entre eux

Résumé

vignette|Le segment ne passe par aucun point du réseau (hormis les points à ses extrémités), ce qui montre que 4 et 9 sont premiers entre eux. En mathématiques, on dit que deux entiers a et b sont premiers entre eux, que a est premier avec b ou premier à b ou encore que a et b sont copremiers (ou encore étrangers) si leur plus grand commun diviseur est égal à 1 ; en d'autres termes, s'ils n'ont aucun diviseur autre que 1 et –1 en commun. De manière équivalente, ils sont premiers entre eux s'ils n'ont aucun facteur premier en commun. Par exemple, 6 et 35 sont premiers entre eux, mais 6 et 27 ne le sont pas parce qu'ils sont tous les deux divisibles par 3. Le nombre 1 est premier avec tout entier, tandis que 0 est uniquement premier avec 1 et –1. Cette notion a été introduite dans le livre VII des Éléments d'Euclide. Des notations standard pour deux entiers a et b premiers entre eux sont : pgcd(a, b) = 1 ou a∧b = 1. Ronald Graham, Donald Knuth et Oren Patas

Source officielle

https://fr.wikipedia.org/wiki/Nombres_premiers_entre_eux

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (7)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (47)

Concepts associés

Chargement

Cours associés (19)

Cours associés

Chargement

Séances de cours associées (57)

Séances de cours associées

Chargement

Mirror symmetry for moduli spaces of Higgs bundles via $p$-adic integration

Michael Gröchenig, Dimitri Stelio Wyss

We prove the Topological Mirror Symmetry Conjecture by Hausel-Thaddeus for smooth moduli spaces of Higgs bundles of type

SL_n

and

PGL_n

. More precisely, we establish an equality of stringy Hodge numbers for certain pairs of algebraic orbifolds generically fibred into dual abelian varieties. Our proof utilises

p

-adic integration relative to the fibres, and interprets canonical gerbes present on these moduli spaces as characters on the Hitchin fibres using Tate duality. Furthermore we prove for

d

coprime to

n

, that the number of rank

n

Higgs bundles of degree

d

over a fixed curve defined over a finite field, is independent of

d

. This proves a conjecture by Mozgovoy--Schiffman in the coprime case.

2017

Chargement

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time. It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2 + epsilon. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to DEMAND MULTICUT ON TREES and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1 + epsilon, and then solve its resulting instances up to a factor of 2 + epsilon by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods. We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.

ASSOC COMPUTING MACHINERY2021

Chargement

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set in that is not an axis-aligned rectangle and for any positive integer produces a family of sets, each obtained by an independent horizontal and vertical scaling and translation of , such that no three sets in pairwise intersect and . This provides a negative answer to a question of Gyarfas and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.

Springer US2013

Chargement

Mirror symmetry for moduli spaces of Higgs bundles via $p$-adic integration

Michael Gröchenig, Dimitri Stelio Wyss

We prove the Topological Mirror Symmetry Conjecture by Hausel-Thaddeus for smooth moduli spaces of Higgs bundles of type

SL_n

and

PGL_n

. More precisely, we establish an equality of stringy Hodge numbers for certain pairs of algebraic orbifolds generically fibred into dual abelian varieties. Our proof utilises

p

-adic integration relative to the fibres, and interprets canonical gerbes present on these moduli spaces as characters on the Hitchin fibres using Tate duality. Furthermore we prove for

d

coprime to

n

, that the number of rank

n

Higgs bundles of degree

d

over a fixed curve defined over a finite field, is independent of

d

. This proves a conjecture by Mozgovoy--Schiffman in the coprime case.

2017