Program for U Groups

MA375, Spring 2009, Prof. Walther

This is a program that will list all the cycles of U(x). An example would be:
Input: x = 20 (Finding the cycles of U(20))
Output: U(20) = {1,3,7,9,11,13,17,19}
<1> = {1}
<3> = {1,3,7,9}
<7> = {1,3,7,9}
<9> = {1,9}
<11> = {1,11}
<13> = {1,9,13,17}
<17> = {1,9,13,17}
<19> = {1,19}

Here's the program:

#include <iostream>
#include <cmath>
#include <map>
#include <list>

using namespace std;

int gcd(int a, int b);

int main(int argc, char **argv)
{
	map<int, list<int> > gens;
	map<int, list<int> >::iterator iter;
	list<int>::iterator l_iter;
	int u, p = -1;
	while(1)
	{
		cout << "Enter an integer x (for U(x)): ";
		cin >> u;
		if(u > 1)
			break;
		cout << "Error: x must be greater than 1\n";
	}
	for(int i = 1; i < u; i++)
	{
		if(gcd(i, u) == 1)
		{
			while(p != i)
			{
				gens[i].push_back(p = (p == -1 ? (i*i)%u : (i*p)%u));
			}
			p = -1;
		}		
	}
	iter = gens.begin();
	cout << "U(" << u << ") = {" << (*iter).first;
	iter++;
	for(; iter != gens.end(); iter++)
		cout << "," << (*iter).first;
	cout << "}" << endl;
	for(iter = gens.begin(); iter != gens.end(); iter++)
	{
		(*iter).second.sort();
		l_iter = (*iter).second.begin();
		cout << "<" << (*iter).first << "> = {" << *l_iter;
		l_iter++;
		for(; l_iter != (*iter).second.end(); l_iter++)
		{
			cout << "," << *l_iter;
		}
		cout << "}" << endl;
	}
	system("PAUSE");
}

int gcd(int a, int b)
{
	if(a > b)
		gcd(b, a);
	if(b%a == 0)
		return a;
	else
		return gcd(b%a, a);
}

I can also send you the program if you want to e-mail me at jniederh@purdue.edu

--Jniederh 17:31, 15 February 2009 (UTC)

Back to MA375, Spring 2009, Prof. Walther