Automatic meter reading (AMR) is the technology of automatically collecting consumption, diagnostic, and status data from water meter or energy metering devices (gas, electric) and transferring that data to a central database for billing, troubleshooting, and analyzing. This technology mainly saves utility providers the expense of periodic trips to each physical location to read a meter. Another advantage is that billing can be based on near real-time consumption rather than on estimates based on past or predicted consumption. This timely information coupled with analysis can help both utility providers and customers better control the use and production of electric energy, gas usage, or water consumption. AMR technologies include handheld, mobile and network technologies based on telephony platforms (wired and wireless), radio frequency (RF), or powerline transmission. == Technologies == === Touch technology === With touch-based AMR, a meter reader carries a handheld computer or data collection device with a wand or probe. The device automatically collects the readings from a meter by touching or placing the read probe close to a reading coil enclosed in the touchpad. When a button is pressed, the probe sends an interrogate signal to the touch module to collect the meter reading. The software in the device matches the serial number to one in the route database, and saves the meter reading for later download to a billing or data collection computer. Since the meter reader still has to go to the site of the meter, this is sometimes referred to as "on-site" AMR. Another form of contact reader uses a standardized infrared port to transmit data. Protocols are standardized between manufacturers by such documents as ANSI C12.18 or IEC 61107. === AMR hosting === AMR hosting is a back-office solution which allows a user to track their electricity, water, or gas consumption over the Internet. All data is collected in near real-time, and is stored in a database by data acquisition software. The user can view the data via a web application, and can analyze the data using various online analysis tools such as charting load profiles, analyzing tariff components, and verify their utility bill. === Radio frequency network === Radio frequency based AMR can take many forms. The more common ones are handheld, mobile, satellite and fixed network solutions. There are both two-way RF systems and one-way RF systems in use that use both licensed and unlicensed RF bands. In a two-way or "wake up" system, a radio signal is normally sent to an AMR meter's unique serial number, instructing its transceiver to power-up and transmit its data. The meter transceiver and the reading transceiver both send and receive radio signals. In a one-way "bubble-up" or continuous broadcast type system, the meter transmits continuously and data is sent every few seconds. This means the reading device can be a receiver only, and the meter a transmitter only. Data travels only from the meter transmitter to the reading receiver. There are also hybrid systems that combine one-way and two-way techniques, using one-way communication for reading and two-way communication for programming functions. RF-based meter reading usually eliminates the need for the meter reader to enter the property or home, or to locate and open an underground meter pit. The utility saves money by increased speed of reading, has less liability from entering private property, and has fewer missed readings from being unable to access the meter. The technology based on RF is not readily accepted everywhere. In several Asian countries, the technology faces a barrier of regulations in place pertaining to use of the radio frequency of any radiated power. For example, in India the radio frequency which is generally in ISM band is not free to use even for low power radio of 10 mW. The majority of manufacturers of electricity meters have radio frequency devices in the frequency band of 433/868 MHz for large scale deployment in European countries. The frequency band of 2.4 GHz can be now used in India for outdoor as well as indoor applications, but few manufacturers have shown products within this frequency band. Initiatives in radio frequency AMR in such countries are being taken up with regulators wherever the cost of licensing outweighs the benefits of AMR. ==== Handheld ==== In handheld AMR, a meter reader carries a handheld computer with a built-in or attached receiver/transceiver (radio frequency or touch) to collect meter readings from an AMR capable meter. This is sometimes referred to as "walk-by" meter reading since the meter reader walks by the locations where meters are installed as they go through their meter reading route. Handheld computers may also be used to manually enter readings without the use of AMR technology as an alternate but this will not support exhaustive data which can be accurately read using the meter reading electronically. ==== Mobile ==== Mobile or "drive-by" meter reading is where a reading device is installed in a vehicle. The meter reader drives the vehicle while the reading device automatically collects the meter readings. Often, for mobile meter reading, the reading equipment includes navigational and mapping features provided by GPS and mapping software. With mobile meter reading, the reader does not normally have to read the meters in any particular route order, but just drives the service area until all meters are read. Components often consist of a laptop or proprietary computer, software, RF receiver/transceiver, and external vehicle antennas. ==== Satellite ==== Transmitters for data collection satellites can be installed in the field next to existing meters. The satellite AMR devices communicate with the meter for readings, and then sends those readings over a fixed or mobile satellite network. This network requires a clear view to the sky for the satellite transmitter/receiver, but eliminates the need to install fixed towers or send out field technicians, thereby being particularly suited for areas with low geographic meter density. ==== RF technologies commonly used for AMR ==== Narrow Band (single fixed radio frequency) Spread spectrum Direct-sequence spread spectrum (DSSS) Frequency-hopping spread spectrum (FHSS) There are also meters using AMR with RF technologies such as cellular phone data systems, Zigbee, Bluetooth, Wavenis and others. Some systems operate with U.S. Federal Communications Commission (FCC) licensed frequencies and others under FCC Part 15, which allows use of unlicensed radio frequencies. ==== Wi-Fi ==== WiSmart is a versatile platform which can be used by a variety of electrical home appliances in order to provide wireless TCP/IP communication using the 802.11 b/g protocol. Devices such as the Smart Thermostat permit a utility to lower a home's power consumption to help manage power demand. The city of Corpus Christi became one of the first cities in the United States to implement citywide Wi-Fi, which had been free until May 31, 2007, mainly to facilitate AMR after a meter reader was attacked by a dog. Today many meters are designed to transmit using Wi-Fi, even if a Wi-Fi network is not available, and they are read using a drive-by local Wi-Fi hand held receiver. The meters installed in Corpus Christi are not directly Wi-Fi enabled, but rather transmit narrow-band burst telemetry on the 460 MHz band. This narrow-band signal has much greater range than Wi-Fi, so the number of receivers required for the project are far fewer. Special receiver stations then decode the narrow-band signals and resend the data via Wi-Fi. Most of the automated utility meters installed in the Corpus Christi area are battery powered. Wi-Fi technology is unsuitable for long-term battery-powered operation. === Power line communication === PLC is a method where electronic data is transmitted over power lines back to the substation, then relayed to a central computer in the utility's main office. This would be considered a type of fixed network system—the network being the distribution network which the utility has built and maintains to deliver electric power. Such systems are primarily used for electric meter reading. Some providers have interfaced gas and water meters to feed into a PLC type system. == Brief history == In 1972, Theodore George "Ted" Paraskevakos, while working with Boeing in Huntsville, Alabama, developed a sensor monitoring system which used digital transmission for security, fire and medical alarm systems as well as meter reading capabilities for all utilities. This technology was a spin-off of the automatic telephone line identification system, now known as caller ID. In 1974, Paraskevakos was awarded a U.S. patent for this technology. In 1977, he launched Metretek, Inc., which developed and produced the first fully automated, commercially available remote meter reading and load management system. Since this system was developed pre-Internet, Metret
Dave's Redistricting
Dave's Redistricting App (DRA) is an online web app originally created by Dave Bradlee that allows anyone to simulate redistricting a U.S. state's congressional and legislative districts. == Purpose == According to Bradlee, the software was designed to "put power in people's hands," and so that they "can see how the process works, so it's a little less mysterious than it was 10 years ago." Bradlee has noticed that many citizens are taking this process seriously and using his app to create legitimate redistricting maps that could be put in place. Some websites have called Bradlee the pioneer and cause of the rise of do-it-yourself redistricting. States such as Montana in 2021 allowed the general population to use it to submit redistricting proposals following the 2020 United States Census. Dave's Redistricting has frequently been mentioned as a resource that can be used to combat gerrymandering, given that the public has free access to it. Political science firms such as FiveThirtyEight have used the website to draw examples of gerrymandered districts, including on their famous Atlas of Redistricting. Dave Bradlee built the first generation of DRA. DRA 2020 is built by a small team of volunteers—Dave Bradlee, Terry Crowley, Alec Ramsay, and David Rinn—all with a shared passion for technology & democracy and all Microsoft veterans. Their mission is to empower civic organizations and citizen activists to advocate for fair congressional and legislative districts and increased transparency in the redistricting process. == Functions == Users can redraw the congressional and state legislative districts for all 50 states, the District of Columbia, and Puerto Rico using a variety of census and election datasets including Cook PVI. Maps can be optimized for different criteria. DRA 2020 added several major features to the first generation app: Sharing & collaborative editing of maps, like Google Docs Multiple statewide elections for all 50 states including the ability to import your own data Comprehensive analytics for evaluating and comparing maps Custom overlays, and Block-level editing DRA remains free to use. == Versions == 2.2: This uses Bing Maps, an outdated software that projects the districts of a single state onto a map of the United States. 2.5: After Bing Maps announced that it would no longer be updating for the foreseen future, the U.S. Map feature was removed. DRA 2020: At the end of 2018, a beta version of 2020 was released. This version that did not require Microsoft Silverlight and could be used in any web browser. DRA 2020 has been under continuous development since and is built using React (JavaScript library), Mapbox, OpenStreetMap, TypeScript, Node.js, Amazon Web Services, as well as many open source components, tools, and icons.
Knowledge spillover
Knowledge spillover is an exchange of ideas among individuals. Knowledge spillover is usually replaced by terminations of technology spillover, R&D spillover and/or spillover (economics) when the concept is specific to technology management and innovation economics. In knowledge management economics, knowledge spillovers are non-rival knowledge market costs incurred by a party not agreeing to assume the costs that has a spillover effect of stimulating technological improvements in a neighbor through one's own innovation. Such innovations often come from specialization within an industry. There are two kinds of knowledge spillovers: internal and external. Internal knowledge spillover occurs if there is a positive impact of knowledge between individuals within an organization that produces goods and/or services. An external knowledge spillover occurs when the positive impact of knowledge is between individuals outside of a production organization. Marshall–Arrow–Romer (MAR) spillovers, Porter spillovers and Jacobs spillovers are three types of spillovers. == Conceptualizations == === Marshall–Arrow–Romer === Marshall–Arrow–Romer (MAR) spillover has its origins in 1890, where the English economist Alfred Marshall developed a theory of knowledge spillovers. Knowledge spillovers later were extended by economists Kenneth Arrow (1962) and Paul Romer (1986). In 1992, Edward Glaeser, Hedi Kallal, José Scheinkman, and Andrei Shleifer pulled together the Marshall–Arrow–Romer views on knowledge spillovers and accordingly named the view MAR spillover in 1992. Under the Marshall–Arrow–Romer (MAR) spillover view, the proximity of firms within a common industry often affects how well knowledge travels among firms to facilitate innovation and growth. The closer the firms are to one another, the greater the MAR spillover. The exchange of ideas is largely from employee to employee, in that employees from different firms in an industry exchange ideas about new products and new ways to produce goods. The opportunity to exchange ideas that lead to innovations key to new products and improved production methods. Research on the Cambridge IT Cluster (UK) suggests that technological knowledge spillovers might only happen rarely and are less important than other cluster benefits such as labour market pooling. === Porter === Porter (1990), like MAR, argues that knowledge spillovers in specialized, geographically concentrated industries stimulate growth. He insists, however, that local competition, as opposed to local monopoly, fosters the pursuit and rapid adoption of innovation. He gives examples of Italian ceramics and gold jewellery industries, in which hundreds of firms are located together and fiercely compete to innovate since the alternative to innovation is demise. Porter's externalities are maximized in cities with geographically specialized, competitive industries. === Jacobs === Under the Jacobs spillover view, the proximity of firms from different industries affect how well knowledge travels among firms to facilitate innovation and growth. This is in contrast to MAR spillovers, which focus on firms in a common industry. The diverse proximity of a Jacobs spillover brings together ideas among individuals with different perspectives to encourage an exchange of ideas and foster innovation in an industrially diverse environment. Developed in 1969 by urbanist Jane Jacobs and John Jackson the concept that Detroit’s shipbuilding industry from the 1830s was the critical antecedent leading to the 1890s development of the auto industry in Detroit since the gasoline engine firms easily transitioned from building gasoline engines for ships to building them for automobiles. == Incoming and outgoing spillovers == Knowledge spillover has asymmetric directions. The focal entity and receives or outflows know-how to others, creating incoming and outgoing spillovers. Cassiman and Veugelers (2002) use survey data and estimate incoming and outgoing spillover and study the economic impacts. Incoming spillover increases growth opportunity and productivity improvements of receivers, while outgoing spillover leads to free rider problem in the technology competition. Chen et al. (2013) use econometric method to gauge incoming spillover, a way that applies for all companies without survey. They find that incoming spillover explains R&D profits of industrial firms. == Policy implications == As information is largely non-rival in nature, certain measures must be taken to ensure that, for the originator, the information remains a private asset. As the market cannot do this efficiently, public regulations have been implemented to facilitate a more appropriate equilibrium. As a result, the concept of intellectual property rights have developed and ensure the ability of entrepreneurs to temporarily hold on to the profitability of their ideas through patents, copyrights, trade secrets, and other governmental safeguards. Conversely, such barriers to entry prevent the exploitation of informational developments by rival firms within an industry. For example, Wang (2023) indicates that technology spillovers are reduced by 27% to 51% when trade secrets laws are implemented by the Uniform Trade Secrets Act in the US. On the other hand, when the research and development of a private firm results in a social benefit, unaccounted for within the market price, often greater than the private return of the firm's research, then a subsidy to offset the underproduction of that benefit might be offered to the firm in return for its continued output of that benefit. Government subsidies are often controversial, and while they might often result in a more appropriate social equilibrium, they could also lead to undesirable political repercussions as such a subsidy must come from taxpayers, some of whom may not directly benefit from the researching firm's subsidized knowledge spillover. The concept of knowledge spillover is also used to justify subsidies to foreign direct investment, as foreign investors help diffuse technology among local firms. == Examples == Business parks are a good specific example of concentrated businesses that may benefit from MAR spillover. Many semiconductor firms intentionally located their research and development facilities in Silicon Valley to take advantage of MAR spillover. In addition, the film industry in Los Angeles, California, and elsewhere relies on a geographic concentration of specialists (directors, producers, scriptwriters, and set designers) to bring together narrow aspects of movie-making into a final product. A general example of a knowledge spillover could be the collective growth associated with the research and development of online social networking tools like Facebook, YouTube, and Twitter. Such tools have not only created a positive feedback loop, and a host of originally unintended benefits for their users, but have also created an explosion of new software, programming platforms, and conceptual breakthroughs that have perpetuated the development of the industry as a whole. The advent of online marketplaces, the utilization of user profiles, the widespread democratization of information, and the interconnectivity between tools within the industry have all been products of each tool's individual developments. These developments have since spread outside the industry into the mainstream media as news and entertainment firms have developed their own market feedback applications within the tools themselves, and their own versions of online networking tools (e.g. CNN’s iReport).
Scriptella
Scriptella is an open source extract transform load (ETL) and script execution tool written in Java. It allows the use of SQL or another scripting language suitable for the data source to perform required transformations. Scriptella does not offer any graphical user interface. == Typical use == Database migration. Database creation/update scripts. Cross-database ETL operations, import/export. Alternative for Ant
Kleene's algorithm
In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given nondeterministic finite automaton (NFA) into a regular expression. Together with other conversion algorithms, it establishes the equivalence of several description formats for regular languages. Alternative presentations of the same method include the "elimination method" attributed to Brzozowski and McCluskey, the algorithm of McNaughton and Yamada, and the use of Arden's lemma. == Algorithm description == According to Gross and Yellen (2004), the algorithm can be traced back to Kleene (1956). A presentation of the algorithm in the case of deterministic finite automata (DFAs) is given in Hopcroft and Ullman (1979). The presentation of the algorithm for NFAs below follows Gross and Yellen (2004). Given a nondeterministic finite automaton M = (Q, Σ, δ, q0, F), with Q = { q0,...,qn } its set of states, the algorithm computes the sets Rkij of all strings that take M from state qi to qj without going through any state numbered higher than k. Here, "going through a state" means entering and leaving it, so both i and j may be higher than k, but no intermediate state may. Each set Rkij is represented by a regular expression; the algorithm computes them step by step for k = -1, 0, ..., n. Since there is no state numbered higher than n, the regular expression Rn0j represents the set of all strings that take M from its start state q0 to qj. If F = { q1,...,qf } is the set of accept states, the regular expression Rn01 | ... | Rn0f represents the language accepted by M. The initial regular expressions, for k = -1, are computed as follows for i≠j: R−1ij = a1 | ... | am where qj ∈ δ(qi,a1), ..., qj ∈ δ(qi,am) and as follows for i=j: R−1ii = a1 | ... | am | ε where qi ∈ δ(qi,a1), ..., qi ∈ δ(qi,am) In other words, R−1ij mentions all letters that label a transition from i to j, and we also include ε in the case where i=j. After that, in each step the expressions Rkij are computed from the previous ones by Rkij = Rk-1ik (Rk-1kk) Rk-1kj | Rk-1ij Another way to understand the operation of the algorithm is as an "elimination method", where the states from 0 to n are successively removed: when state k is removed, the regular expression Rk-1ij, which describes the words that label a path from state i>k to state j>k, is rewritten into Rkij so as to take into account the possibility of going via the "eliminated" state k. By induction on k, it can be shown that the length of each expression Rkij is at most 1/3(4k+1(6s+7) - 4) symbols, where s denotes the number of characters in Σ. Therefore, the length of the regular expression representing the language accepted by M is at most 1/3(4n+1(6s+7)f - f - 3) symbols, where f denotes the number of final states. This exponential blowup is inevitable, because there exist families of DFAs for which any equivalent regular expression must be of exponential size. In practice, the size of the regular expression obtained by running the algorithm can be very different depending on the order in which the states are considered by the procedure, i.e., the order in which they are numbered from 0 to n. == Example == The automaton shown in the picture can be described as M = (Q, Σ, δ, q0, F) with the set of states Q = { q0, q1, q2 }, the input alphabet Σ = { a, b }, the transition function δ with δ(q0,a)=q0, δ(q0,b)=q1, δ(q1,a)=q2, δ(q1,b)=q1, δ(q2,a)=q1, and δ(q2,b)=q1, the start state q0, and set of accept states F = { q1 }. Kleene's algorithm computes the initial regular expressions as After that, the Rkij are computed from the Rk-1ij step by step for k = 0, 1, 2. Kleene algebra equalities are used to simplify the regular expressions as much as possible. Step 0 Step 1 Step 2 Since q0 is the start state and q1 is the only accept state, the regular expression R201 denotes the set of all strings accepted by the automaton.
Xiaomi MiMo
Xiaomi MiMo is a family of large language models (LLMs) developed by Xiaomi. It was initially released in April 2025 with the MiMo-7B model. Currently, MiMo is available for developers through API service. It is used as the key AI model in Xiaomi's "Human x Car x Home" ecosystem. == Development == Xiaomi developed MiMo as a reasoning-focused language model. Its development team was led by Luo Fuli, who had previously worked at DeepSeek before joining Xiaomi in late 2025. The model was trained using multi-token prediction and reinforcement learning, with a particular emphasis on mathematical reasoning and code generation tasks. In March 2026, Xiaomi CEO Lei Jun announced that the company planned to invest at least US$8.7 billion in artificial intelligence over the following three years. == Models == === List of models === === MiMo-7B === MiMo-7B is the first model of this LLM. The base model, MiMo-7B-Base, was pre-trained on approximately 25 trillion tokens using web pages, academic papers, books, and synthetic reasoning data. MiMo-7B-RL underwent supervised fine-tuning and reinforcement learning on 130,000 mathematics and code problems. MiMo-7B-RL-0530 was released in May 2025. It scaled the fine-tuning dataset from 500,000 to 6 million instances and extended the RL window from 32,000 to 48,000 tokens and improved AIME 2024 scores from 68.2 to 80.1. MiMo-VL-7B was a vision-language model combining a Vision Transformer encoder with the MiMo-7B backbone. It was trained in four stages consuming 2.4 trillion tokens. Its reinforcement learning variant used Mixed On-Policy Reinforcement Learning (MORL) which integrated reward signals across perception, grounding, and reasoning. Xiaomi also released MiMo-Audio-7B, an audio-language model for voice conversion, style transfer, and speech editing. === MiMo-V2-Flash === MiMo-V2-Flash was launched in December 2025. It is a open-sourced Mixture-of-experts model with 309 billion total parameters and 15 billion active parameters. It was trained on 27 trillion tokens using FP8 mixed precision. It used hybrid attention interleaving Sliding Window and Global Attention at a 5:1 ratio. === MiMo-V2-Pro === Xiaomi publicly introduced MiMo-V2-Pro on 18 March 2026. It has over 1 trillion total parameters, 42 billion active, and a 1-million-token context window. Before the official release, the model had appeared anonymously on OpenRouter under the codename "Hunter Alpha," where it drew substantial usage and topped daily charts for several days, according to Xiaomi and Reuters. During its listing on OpenRouter, the model reportedly processed over one trillion tokens in total usage. Xiaomi later said Hunter Alpha was an early internal test build of MiMo-V2-Pro, and Reuters reported that the model had been mistaken by some users for a possible DeepSeek system before Xiaomi confirmed its origin. The model was released as a proprietary API product, and Luo Fuli stated that Xiaomi intended to open-source a variant at an unspecified future date. Xiaomi has partnered with several API web platforms like OpenClaw to launch the model. All these websites initially offered a free trial of this model for a week, but due to the overwhelming response, Xiaomi later extended the free trial period of the model until 2 April 2026. === MiMo-V2-Omni === Alongside MiMo-V2-Pro, Xiaomi launched MiMo-V2-Omni on 18 March 2026. It handles image, video, audio, and text inputs. Before the official release, it was codenamed "Healer Alpha" in OpenRouter. === MiMo-V2-TTS === On the same date as the release of MiMo-V2-Pro and MiMo-V2-Omni, a Text-to-Speech model named MiMo-V2-TTS was released also. It is a speech synthesis model. It was trained on audio data, which makes it capable of emotional transitions, mid-sentence tone shifts, singing, and synthesis of regional dialects like Sichuan, Cantonese, Henan, and Taiwanese. == Licensing == Xiaomi has used different licensing approaches for different models in the MiMo family. The MiMo-7B series and MiMo-V2-Flash were released as open-weight models. MiMo-V2-Flash was published under the MIT license with model weights and inference code available on Hugging Face. MiMo-V2-Pro and MiMo-V2-Omni were released as proprietary models. It was accessible through Xiaomi's API platform and third-party API providers. Luo Fuli stated that Xiaomi intended to open-source a variant of MiMo-V2-Pro. Although, she did not specify any timeline. MiMo-V2-TTS was released as a proprietary model with no publicly available weights.
Certifying algorithm
In theoretical computer science, a certifying algorithm is an algorithm that outputs, together with a solution to the problem it solves, a proof that the solution is correct. A certifying algorithm is said to be efficient if the combined runtime of the algorithm and a proof checker is slower by at most a constant factor than the best known non-certifying algorithm for the same problem. The proof produced by a certifying algorithm should be in some sense simpler than the algorithm itself, for otherwise any algorithm could be considered certifying (with its output verified by running the same algorithm again). Sometimes this is formalized by requiring that a verification of the proof take less time than the original algorithm, while for other problems (in particular those for which the solution can be found in linear time) simplicity of the output proof is considered in a less formal sense. For instance, the validity of the output proof may be more apparent to human users than the correctness of the algorithm, or a checker for the proof may be more amenable to formal verification. Implementations of certifying algorithms that also include a checker for the proof generated by the algorithm may be considered to be more reliable than non-certifying algorithms. For, whenever the algorithm is run, one of three things happens: it produces a correct output (the desired case), it detects a bug in the algorithm or its implication (undesired, but generally preferable to continuing without detecting the bug), or both the algorithm and the checker are faulty in a way that masks the bug and prevents it from being detected (undesired, but unlikely as it depends on the existence of two independent bugs). == Examples == Many examples of problems with checkable algorithms come from graph theory. For instance, a classical algorithm for testing whether a graph is bipartite would simply output a Boolean value: true if the graph is bipartite, false otherwise. In contrast, a certifying algorithm might output a 2-coloring of the graph in the case that it is bipartite, or a cycle of odd length if it is not. Any graph is bipartite if and only if it can be 2-colored, and non-bipartite if and only if it contains an odd cycle. Both checking whether a 2-coloring is valid and checking whether a given odd-length sequence of vertices is a cycle may be performed more simply than testing bipartiteness. Analogously, it is possible to test whether a given directed graph is acyclic by a certifying algorithm that outputs either a topological order or a directed cycle. It is possible to test whether an undirected graph is a chordal graph by a certifying algorithm that outputs either an elimination ordering (an ordering of all vertices such that, for every vertex, the neighbors that are later in the ordering form a clique) or a chordless cycle. And it is possible to test whether a graph is planar by a certifying algorithm that outputs either a planar embedding or a Kuratowski subgraph. The extended Euclidean algorithm for the greatest common divisor of two integers x and y is certifying: it outputs three integers g (the divisor), a, and b, such that ax + by = g. This equation can only be true of multiples of the greatest common divisor, so testing that g is the greatest common divisor may be performed by checking that g divides both x and y and that this equation is correct.