Nie do końca rozumiem pytania (zdefiniuj "zależnych") - na przykład ja bym powiedział że liczby względnie pierwsze są właśnie wobec siebie "niezależne".
Jeśli rozmawiamy o najbardziej ogólnym przypadku, gdzie zależność to dowolna (symetryczna) relacja między dwoma elementami, to możemy zamodelować ten problem jako graf.
Wierzchołki w grafie to elementy z Twojego zbioru, a dwa wierzchołki łączy krawędź wtedy kiedy występuje między nimi ta dowolna relacja. Szukamy największej takiej grupy wierzchołków G, że każde dwa wierzchołki z G są połączone krawędzią.
Na tak postawiony problem jest dość klasyczny algorytm grafowy...
http://en.wikipedia.org/wiki/Clique_problem
...niestety NP zupełny.
W trywialny sposób można przeprowadzić redukcje w drugą stronę (czyli z dowolnego zbioru elementów z ustaloną relacją na graf), więc o ile czegoś nie przeoczyłem, wynika z tego że tak postawiony ogólny problem jest NP zupełny.
Wiesz coś może więcej o tej relacji 'zależności' dla której chcesz wykonywać algorytm (np. gdyby była przechodnia, ale to nie pasuje do podanego przykładu liczb względnie pierwszych)? Może da się jednak w bardziej specyficznym przypadku coś zrobić.
(*NP zupełny ~= nie do zrobienia szybko, o ile nie zajdzie BARDZO poważny przełom w informatyce)