Learning Primality from Modular-Inverse Graphs

Abstract

This work investigates whether graph neural networks (GNNs) can learn to distinguish prime from composite integers through graph-based representations of numbers. Each integer is represented by a modular-inverse graph whose structure is determined by multiplicative inverse relations modulo the integer. Importantly, the same graph-construction rule is applied to every integer, independently of whether it is prime or composite, and no primality label is explicitly incorporated into the graph representation. We provide a mathematical justification for the proposed approach by proving that, despite this uniform construction, systematic structural differences emerge between the modular-inverse graphs associated with prime and composite integers. In particular, prime integers produce graphs with the maximum possible number of edges connecting distinct nonzero vertices and no isolated nonzero vertices, whereas composite integers produce fewer such edges and contain isolated nonzero vertices. We further analyze the message-passing mechanisms of GraphSAGE and Graph Convolutional Networks (GCN), showing how these structural differences can be preserved or lost depending on the aggregation mechanism. Based on this mathematical characterization, GraphSAGE and GCN are comparatively evaluated on a dataset of 10,000 integers ranging from 2 to 10,001. Models trained on the modular-inverse graphs of smaller integers are evaluated on those of larger, previously unseen integers, with balanced accuracy (BA) used to account for the class imbalance between prime and composite numbers. The selected GraphSAGE architecture achieves a mean BA of 99.89% across three random seeds on the test set, whereas GCN remains at 50.00% validation BA across all evaluated configurations and seeds. These results align with the mathematical analysis and demonstrate that the ability to learn structural differences associated with primality from modular-inverse graphs depends critically on the GNN message-passing mechanism.